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
n + O(1) 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.
 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 GoodmanPollack Festschrift, pages 139156.
Springer, 2003.
The Open Problems Project  September 19, 2017