Next: Problem 67: Fair Partitioning of Convex Polygons
Previous: Problem 65: Magic Configurations
Let \rho(S) be the fewest number of reflex vertices in a polygonization of a 2D point set S, i.e., the fewest reflexivities of any simple polygon whose vertex set is S. Let \rho(n) be the maximum of \rho(S) over all sets S with n points. What is \rho(n)?
Open.
In [AFH+03] the authors prove that \lfloor n/4 \rfloor \le \rho(n) \le \lceil n/2 \rceil and conjecture that \rho(n) = \lfloor n/4 \rfloor. The upper bound was recently improved to \frac{5}{12} n + O(1) \approx 0.4167 n in [AAK09].
Problem 16: Simple Polygonalizations.
polygons; point sets.
J. O’Rourke, 3 Aug. 2006; 16 Jul 2008.
Eyal Ackerman, Oswin Aichholzer, and Balazs Keszegh. Improved upper bounds on the reflexivity of point sets. Comput. Geom.: Theory Appl., 42(3), April 2009.
Esther M. Arkin, Sándor P. Fekete, Ferran Hurtado, Joseph S. B. Mitchell, Marc Noy, Vera Sacristán, and Saurabh Sethia. On the reflexivity of point sets. In B. Aronov, S. Basu, J. Pach, and M. Sharir, editors, Discrete and Computational Geometry: The Goodman-Pollack Festschrift, pages 139–156. Springer, 2003.