direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Preprints 2000

On the Reflexivity of Point Sets
Zitatschlüssel Report-694-2000
Autor Esther M. Arkin and Sándor P. Fekete and Ferran Hurtado and Joseph S. B. Mitchell and Marc Noy and Vera Sacristán and Saurabh Sethia
Jahr 2000
Nummer 694
Notiz Submitted for publication
Institution Technische Universität Berlin, Institut für Mathematik
Zusammenfassung We introduce a new measure for planar point sets $S$. Intuitively, it describes the combinatorial distance from a convex set: The reflexivity $\rho(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 $\kappa_1(S)$ of a planar point set, which is the smallest number of convex chains that cover $S$, and the convex partition number $\kappa_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.
Typ der Publikation Preprint
Download Bibtex Eintrag