  We introduce a new measure for planar point sets S that captures a
combinatorial distance that S is from being a convex set: The reflexivity
rho(S) of S is given by the smallest number of reflex vertices in a simple
polygonalization of S. We prove various combinatorial bounds and provide
efficient algorithms to compute reflexivity, both exactly (in special cases)
and approximately (in general). Our study considers also some closely related
quantities, such as the convex cover number kappa_c(S) of a planar point set,
which is the smallest number of convex chains that cover S, and the convex
partition number kappa_p(S), which is given by the smallest number of convex
chains with pairwise-disjoint convex hulls that cover S. We have proved that it
is NP-complete to determine the convex cover or the convex partition number and
have given logarithmic-approximation algorithms for determining each.
