Improved upper bounds on the reflexivity of point sets

AbstractGiven 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. [E.M. Arkin, S.P. Fekete, F. Hurtado, J.S.B. Mitchell, M. Noy, V. Sacristán, S. Sethia, On the reflexivity of point sets, in: B. Aronov, S. Basu, J. Pach M. Sharir (Eds.), Discrete and Computational Geometry: The Goodman–Pollack Festschrift, Springer, 2003, pp. 139–156] 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 37n+O(1)≈0.4286n. Using computer-aided abstract order type extension the upper bound can be further improved to 512n+O(1)≈0.4167n. We also present an algorithm to compute polygonalizations with at most this number of reflex vertices in O(nlogn) time