TY - GEN
T1 - On the reflexivity of point sets
AU - Arkin, Esther M.
AU - Fekete, Sándor P.
AU - Hurtado, Ferran
AU - Mitchell, Joseph S.B.
AU - Noy, Marc
AU - Sacristán, Vera
AU - Sethia, Saurabh
N1 - Publisher Copyright: © Springer-Verlag Berlin Heidelberg 2001.
PY - 2001
Y1 - 2001
N2 - 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 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 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 logarithmicapproximation algorithms for determining each.
AB - 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 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 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 logarithmicapproximation algorithms for determining each.
UR - https://www.scopus.com/pages/publications/84958063610
U2 - 10.1007/3-540-44634-6_18
DO - 10.1007/3-540-44634-6_18
M3 - Conference contribution
SN - 3540424237
SN - 9783540424239
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 192
EP - 204
BT - Algorithms and Data Structures - 7th International Workshop, WADS 2001, Proceedings
A2 - Dehne, Frank
A2 - Sack, Jorg-Rudiger
A2 - Tamassia, Roberto
PB - Springer Verlag
T2 - 7th International Workshop on Algorithms and Data Structures, WADS 2001
Y2 - 8 August 2001 through 10 August 2001
ER -