Improved Upper Bounds on the Reflexivity of Point Sets.
Eyal Ackerman, Oswin Aichholzer, Balázs Keszegh · 2007
Given a set S of n points in the plane, the reflexivity of S, ρ(S), is the minimum number of reflex vertices in a simple polygonalization of S. Arkin et al. [4] proved that ρ(S) ≤ ⌈n/2 ⌉ for any set S, and conjectured that the tight upper bound is ⌊n/4⌋. We show that the reflexivity of any set of n points is at most 3 7n + O(1) ≈ 0.4286n. Using computer-aided abstract order type extension the upper bound can be further improved to 5 12n + O(1) ≈ 0.4167n. We also present an algorithm to compute polygonalizations with at most this number of reflex vertices in O(nlog n) time. 1