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 Ω(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 ∈ N), and obtain
a tight lower bound of Ω(logd−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.
Cartesian product of two sets of n real numbers (for short, grid). First, we prove that every
such grid contains Ω(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 ∈ N), and obtain
a tight lower bound of Ω(logd−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.
| Original language | English |
|---|---|
| Pages (from-to) | 205-233 |
| Journal | Journal of Computational Geometry |
| Volume | 11 |
| Issue number | 2 |
| DOIs | |
| Publication status | Published - 2021 |
Funding
†School of Electrical Engineering and Computer Science, University of Ottawa, Canada, [email protected]. This work has been supported by NSERC. ‡adriandumitrescu. org , [email protected] §Department of Mathematics and Computer Science, TU Eindhoven, The Netherlands, {w.meulemans|[email protected]}@tue.nl ¶LIRMM, CNRS & Université de Montpellier, France, [email protected] ‖Department of Mathematics, California State University Northridge, Los Angeles, CA; and Department of Computer Science, Tufts University, Medford, MA, USA, [email protected] ∗∗School of Computer Science, Carleton University, Canada, [email protected]