Reflexivity of Point Sets

Definitions and mathematical statement

Let $S\subset\mathbb R^2$ consist of $n\ge3$ points with no three collinear. A polygonization is a simple polygon whose vertex set is exactly $S$. A vertex is reflex when its interior angle is strictly greater than $\pi$. Write $r(P)$ for the number of reflex vertices of a polygonization $P$, and define \[ \rho(S)=\min_{P:\ V(P)=S}r(P),\qquad \rho(n)=\max_{S:\ |S|=n}\rho(S). \] The inner minimum chooses the best cyclic order for the particular point set, while the outer maximum chooses the most difficult configuration. Both quantifiers are necessary.

Determine $\rho(n)$ exactly, or obtain sharp asymptotic bounds. The source conjectures the exact expression $\rho(n)=\lfloor n/4\rfloor$. Establishing it requires both a polygonization with at most this many reflex corners for every admissible $S$, and point sets forcing that many corners.

All input points must appear as vertices, including points inside their convex hull. Replacing $S$ by its hull would remove the difficulty and is not allowed. The count measures concave corners, not total angle deficit, and different polygonizations may have different reflex vertices even on the same set.

Short English statement

What is the largest unavoidable number of concave corners when a simple polygon must pass through every point of a prescribed planar set? Is it exactly $\lfloor n/4\rfloor$?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 5500066 (AMR-054-0066), AMR Open Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problems Project - Computational Geometry, Problem 66. Original source indexed by AMR-054-0066. https://topp.openproblem.net/p66.