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)


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
Aantal pagina's6
StatusGepubliceerd - 2018
Evenement34th European Workshop on Computational Geometry (EuroCG2018) - Berlin, Duitsland
Duur: 21 mrt 201823 mrt 2018


Congres34th European Workshop on Computational Geometry (EuroCG2018)
Verkorte titelEuroCG2018
Internet adres


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.