On the Reflexivity of Point Sets

We introduce a new measure for planar point sets S that captures a combinatorial distance that S is from being a convex set: The reflexivityp(S) of S is given by the smallest number of reflex vertices in a simple polygonalization of S. We prove combinatorial bounds on the reflexivity of point sets and study some closely related quantities, including the convex cover number k _c (S) of a planar point set, which is the smallest number of convex chains that cover S, and the convex partition number k _p (S), which is given by the smallest number of convex chains with pairwise-disjoint convex hulls that cover S.