Reflexivity of Point Sets

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)$ ?

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

Reflexivity of Point Sets

Coming soon

Organizer