Reflexivity of planar point sets
For a finite set $S$ of points in the plane, a polygonization of $S$ is a simple polygon whose vertices are exactly the points of $S$. Let $\rho(S)$ be the smallest number of reflex vertices over all polygonizations of $S$, and let $\rho(n)$ be the largest value of $\rho(S)$ over all sets $S$ of $n$ points.
Arkin, Fekete, Hurtado, Mitchell, Noy, Sacristán and Sethia proved that $\lfloor n/4 \rfloor \le \rho(n) \le \lceil n/2 \rceil$, and conjectured that $\rho(n) = \lfloor n/4 \rfloor$. Ackerman, Aichholzer and Keszegh lowered the upper bound to $\frac{5}{12}n + O(1)$.
Problem. Determine $\rho(n)$.
Source: Arkin, Fekete, Hurtado, Mitchell, Noy, Sacristán and Sethia (2003); Problem 66 of The Open Problems Project (Demaine, Mitchell and O'Rourke).
Imported from topp.openproblem.net.
Classification
- Primary
- MG — Metric Geometry
- Secondary
- CO
- Keywords
- polygonization, reflexivity, reflex vertices, The Open Problems Project
References
@incollection{arkin2003,
author = {Arkin, Esther M. and Fekete, S{\'a}ndor P. and Hurtado, Ferran and Mitchell, Joseph S. B. and Noy, Marc and Sacrist{\'a}n, Vera and Sethia, Saurabh},
title = {On the reflexivity of point sets},
booktitle = {Discrete and Computational Geometry: The Goodman--Pollack Festschrift},
editor = {Aronov, B. and Basu, S. and Pach, J. and Sharir, M.},
publisher = {Springer},
year = {2003},
pages = {139--156},
}
@article{ackerman2009,
author = {Ackerman, Eyal and Aichholzer, Oswin and Keszegh, Bal{\'a}zs},
title = {Improved upper bounds on the reflexivity of point sets},
journal = {Comput. Geom.},
volume = {42},
number = {3},
year = {2009},
doi = {10.1016/j.comgeo.2008.05.004},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-01103, "Reflexivity of planar point sets", clopen.solutions.