License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2019.22
URN: urn:nbn:de:0030-drops-104267
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10426/
Go to the corresponding LIPIcs Volume Portal

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

Convex Polygons in Cartesian Products

pdf-format:
LIPIcs-SoCG-2019-22.pdf (0.6 MB)

Abstract

We study several problems concerning convex polygons whose vertices lie in a Cartesian product of two sets of n real numbers (for short, grid). First, we prove that every such grid contains a convex polygon with Omega(log n) vertices and that this bound is tight up to a constant factor. We generalize this result to d dimensions (for a fixed d in N), and obtain a tight lower bound of Omega(log^{d-1}n) for the maximum number of points in convex position in a d-dimensional grid. Second, we present polynomial-time algorithms for computing the longest convex polygonal chain in a grid that contains no two points with the same x- or y-coordinate. We show that the maximum size of such a convex polygon can be efficiently approximated up to a factor of 2. Finally, we present exponential bounds on the maximum number of convex polygons in these grids, and for some restricted variants. These bounds are tight up to polynomial factors.

BibTeX - Entry

@InProceedings{decarufel_et_al:LIPIcs:2019:10426,
  author =	{Jean-Lou De Carufel and Adrian Dumitrescu and Wouter Meulemans and Tim Ophelders and Claire Pennarun and Csaba D. T{\'o}th and Sander Verdonschot},
  title =	{{Convex Polygons in Cartesian Products}},
  booktitle =	{35th International Symposium on Computational Geometry (SoCG 2019)},
  pages =	{22:1--22:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-104-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{129},
  editor =	{Gill Barequet and Yusu Wang},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/10426},
  URN =		{urn:nbn:de:0030-drops-104267},
  doi =		{10.4230/LIPIcs.SoCG.2019.22},
  annote =	{Keywords: Erd{\"o}s-Szekeres theorem, Cartesian product, convexity, polyhedron, recursive construction, approximation algorithm}
}

Keywords: Erdös-Szekeres theorem, Cartesian product, convexity, polyhedron, recursive construction, approximation algorithm
Collection: 35th International Symposium on Computational Geometry (SoCG 2019)
Issue Date: 2019
Date of publication: 11.06.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI