On convex polygons in cartesian products

Jean-Lou De Carufel, Adrian Dumitrescu, Wouter Meulemans, Tim Ophelders, Claire Pennarun, Cs.D. Tóth, Sander Verdonschot

Onderzoeksoutput: Bijdrage aan congresAbstract

6 Downloads (Pure)

Samenvatting

We study several problems concerning convex polygons whose vertices lie on a grid defined by the Cartesian product of two sets of n real numbers, using each coordinate at most once. First, we prove that all such grids contain a convex polygon with Ω(log n) vertices and that this bound is asymptotically tight. Second, we present two polynomial-time algorithms that find the largest
convex polygon of a restricted type. These algorithms give an approximation of the unrestricted case. It is unknown whether the unrestricted problem can be solved in polynomial time.
Originele taal-2Engels
Pagina's39:1-39:6
Aantal pagina's6
StatusGepubliceerd - 2018
Evenement34th European Workshop on Computational Geometry (EuroCG2018) - Berlin, Duitsland
Duur: 21 mrt 201823 mrt 2018
https://conference.imp.fu-berlin.de/eurocg18/home

Congres

Congres34th European Workshop on Computational Geometry (EuroCG2018)
Verkorte titelEuroCG2018
LandDuitsland
StadBerlin
Periode21/03/1823/03/18
Internet adres

    Vingerafdruk

Citeer dit

De Carufel, J-L., Dumitrescu, A., Meulemans, W., Ophelders, T., Pennarun, C., Tóth, C. D., & Verdonschot, S. (2018). On convex polygons in cartesian products. 39:1-39:6. Abstract van 34th European Workshop on Computational Geometry (EuroCG2018), Berlin, Duitsland.