Reflexivity of Point Sets

For a planar point set $S$ , let $\rho(S)$ be the minimum number of reflex vertices over all simple polygonalizations of $S$ , and define $\rho(n)=\max_{|S|=n}\rho(S)$ . Prove or disprove that $\rho(n)=\lfloor n/4\rfloor$ .

Download

Abstract

Determine the maximum, over planar point sets of size $n$ , of the minimum number of reflex vertices in a polygonalization.

Background and progress

Arkin and coauthors introduced reflexivity and established foundational bounds [Arkin et al., 2003]. Improved results place the worst case between $\lfloor n/4\rfloor$ and $5n/12+O(1)$ [Ackerman et al., 2009]; equality with the lower bound is conjectured. The original problem appears in the Open Problems Project at https://topp.openproblem.net/p66.

Reference papers

On the reflexivity of point setsEsther M. Arkin, Sándor P. Fekete, Ferran Hurtado, Joseph S. B. Mitchell, Marc Noy, Vera Sacristán, Saurabh SethiaDiscrete and Computational Geometry: The Goodman-Pollack Festschrift · 2003
Improved upper bounds on the reflexivity of point setsEyal Ackerman, Oswin Aichholzer, Balázs KeszeghComputational Geometry: Theory and Applications · 2009