next up previous
Next: Problem 67: Fair Partitioning Up: The Open Problems Project Previous: Problem 65: Magic Configurations


Problem 66: Reflexivity of Point Sets

Statement
Let ρ(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 ρ(n) be the maximum of ρ(S) over all sets S with n points. What is ρ(n)?
Origin
[AFH+03]
Status/Conjectures
Open.
Partial and Related Results
In [AFH+03] the authors prove that n/4⌋≤ρ(n)≤⌈n/2⌉ and conjecture that ρ(n) = ⌊n/4⌋. The upper bound was recently improved to $ {\frac{{5}}{{12}}}$n + O(1) $ \approx$ 0.4167n in [AAK08].
Related Open Problems
Problem 16: Simple Polygonalizations.
Categories
polygons; point sets.
Entry Revision History
J. O'Rourke, 3 Aug. 2006; 16 Jul 2008.

Bibliography

AAK08
Eyal Ackerman, Oswin Aichholzer, and Balazs Keszegh.
Improved upper bounds on the reflexivity of point sets.
Comput. Geom.: Theory Appl., 2008.
To appear.

AFH+03
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.



The Open Problems Project - December 04, 2015