Back to Search
Start Over
Convex Polygons in Cartesian Products
- Source :
- Journal of Computational Geometry 11(2) (2021). Special Issue of Selected Papers from SoCG 2019
- Publication Year :
- 2018
-
Abstract
- We study several problems concerning convex polygons whose vertices lie in a Cartesian product of two sets of $n$ real numbers (for short, \emph{grid}). First, we prove that every such grid contains $\Omega(\log n)$ points in convex position and that this bound is tight up to a constant factor. We generalize this result to $d$ dimensions (for a fixed $d\in \mathbb{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 $x$- or $y$-monotone 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 a convex polygon with such unique coordinates can be efficiently approximated up to a factor of $2$. Finally, we present exponential bounds on the maximum number of point sets in convex position in such grids, and for some restricted variants. These bounds are tight up to polynomial factors.<br />Comment: 26 pages, 10 figures, a preliminary version was presented at the 35th International Symposium on Computational Geometry (SoCG 2019)
- Subjects :
- Computer Science - Computational Geometry
Computer Science - Discrete Mathematics
Subjects
Details
- Database :
- arXiv
- Journal :
- Journal of Computational Geometry 11(2) (2021). Special Issue of Selected Papers from SoCG 2019
- Publication Type :
- Report
- Accession number :
- edsarx.1812.11332
- Document Type :
- Working Paper
- Full Text :
- https://doi.org/10.20382/jocg.v11i2a9