On the Reflexivity of Point Sets
Preprint
Abstract
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.Keywords
All Related Versions
This publication has 20 references indexed in Scilit:
- The Crust and the β-Skeleton: Combinatorial Curve ReconstructionGraphical Models and Image Processing, 1998
- Triangulations, visibility graph and reflex vertices of a simple polygonComputational Geometry, 1996
- Generating random polygons with given verticesComputational Geometry, 1996
- On a partition into convex polygonsDiscrete Applied Mathematics, 1996
- Counting convex polygons in planar point setsInformation Processing Letters, 1995
- A Pedestrian Approach to Ray Shooting: Shoot a Ray, Take a WalkJournal of Algorithms, 1995
- Applications of a semi-dynamic convex hull algorithmBIT Numerical Mathematics, 1992
- Searching for empty convex polygonsAlgorithmica, 1990
- Covering convex sets with non-overlapping polygonsDiscrete Mathematics, 1990
- Fast triangulation of the plane with respect to simple polygonsInformation and Control, 1985