Inhalt des Dokuments
Preprint 694-2000
Combinatorial Optimization & Graph Algorithms group (COGA-Preprints)- Title
- On the Reflexivity of Point Sets
- Authors
- Esther M. Arkin, Sándor P. Fekete, Ferran Hurtado, Joseph S. B. Mitchell, Marc Noy, Vera Sacristán, and Saurabh Sethia
- Publication
- Submitted for publication
- Classification
-
MSC: primary: 68U05 Computer graphics; computational geometry secondary: 52C45 Combinatorial complexity of geometric structures - Keywords
-
generalized convexity, angles, simple planar polygons, cover problems, approximation.
- Abstract
-
We introduce a new measure for planar point sets S. Intuitively, it describes the combinatorial distance from a convex set: The reflexivity ρ(S) of S is given by the smallest number of reflex vertices in a simple polygonization 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 naturally takes us into the examination of some closely related quantities, such as the convex cover number κ1(S) of a planar point set, which is the smallest number of convex chains that cover S, and the convex partition number κ2(S), which is given by the smallest number of disjoint convex chains that cover S. We prove that it is NP-complete to determine the convex cover or the convex partition number, and we give logarithmic-approximation algorithms for determining each.
- Source
-
The report may be requested from our secretary Gabriele Klink, email: klink@math.tu-berlin.de
Zusatzinformationen / Extras
Direktzugang
Schnellnavigation zur Seite über Nummerneingabe