TY - GEN
T1 - Geodesic-preserving polygon simplification
AU - Aichholzer, Oswin
AU - Hackl, Thomas
AU - Korman, Matias
AU - Pilz, Alexander
AU - Vogtenhuber, Birgit
N1 - Funding Information:
Research supported by the ESF EUROCORES programme EuroGIGA - ComPoSe, Austrian Science Fund (FWF): I 648-N18 and grant EUI-EURC-2011-4306. T.H. supported by the Austrian Science Fund (FWF): P23629-N18 ‘Combinatorial Problems on Geometric Graphs’. M.K. received support of the Secretary for Universities and Research of the Ministry of Economy and Knowledge of the Government of Catalonia and the European Union. A.P. is recipient of a DOC-fellowship of the Austrian Academy of Sciences at the Institute for Software Technology, Graz University of Technology, Austria.
PY - 2013
Y1 - 2013
N2 - Polygons are a paramount data structure in computational geometry. While the complexity of many algorithms on simple polygons or polygons with holes depends on the size of the input polygon, the intrinsic complexity of the problems these algorithms solve is often related to the reflex vertices of the polygon. In this paper, we give an easy-to-describe linear-time method to replace an input polygon P by a polygon P′ such that (1) P′, contains P, (2) P′, has its reflex vertices at the same positions as P, and (3) the number of vertices of P′ is linear in the number of reflex vertices. Since the solutions of numerous problems on polygons (including shortest paths, geodesic hulls, separating point sets, and Voronoi diagrams) are equivalent for both P and P′, our algorithm can be used as a preprocessing step for several algorithms and makes their running time dependent on the number of reflex vertices rather than on the size of P.
AB - Polygons are a paramount data structure in computational geometry. While the complexity of many algorithms on simple polygons or polygons with holes depends on the size of the input polygon, the intrinsic complexity of the problems these algorithms solve is often related to the reflex vertices of the polygon. In this paper, we give an easy-to-describe linear-time method to replace an input polygon P by a polygon P′ such that (1) P′, contains P, (2) P′, has its reflex vertices at the same positions as P, and (3) the number of vertices of P′ is linear in the number of reflex vertices. Since the solutions of numerous problems on polygons (including shortest paths, geodesic hulls, separating point sets, and Voronoi diagrams) are equivalent for both P and P′, our algorithm can be used as a preprocessing step for several algorithms and makes their running time dependent on the number of reflex vertices rather than on the size of P.
UR - http://www.scopus.com/inward/record.url?scp=84893355167&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84893355167&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-45030-3_2
DO - 10.1007/978-3-642-45030-3_2
M3 - Conference contribution
AN - SCOPUS:84893355167
SN - 9783642450297
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 11
EP - 21
BT - Algorithms and Computation - 24th International Symposium, ISAAC 2013, Proceedings
T2 - 24th International Symposium on Algorithms and Computation, ISAAC 2013
Y2 - 16 December 2013 through 18 December 2013
ER -