×

On the reflexivity of point sets. (English) Zbl 1077.52509

Aronov, Boris (ed.) et al., Discrete and computational geometry. The Goodman-Pollack Festschrift. Berlin: Springer (ISBN 3-540-00371-1/hbk). Algorithms Comb. 25, 139-156 (2003).
Summary: 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 combinatorial bounds on the reflexivity of point sets and study some closely related quantities, including 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\).
For the entire collection see [Zbl 1014.00040].

MSC:

52C10 Erdős problems and related topics of discrete geometry
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
PDFBibTeX XMLCite