Geodesic-preserving polygon simplification

DOI10.1142/S0218195914600097zbMATH Open1331.68239arXiv1309.3858MaRDI QIDQ5261017FDOQ5261017

T. Hackl, Alexander Pilz, Matias Korman, Birgit Vogtenhuber, Oswin Aichholzer

Publication date: 1 July 2015

Published in: International Journal of Computational Geometry & Applications (Search for Journal in Brave)

Abstract: 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 $mathcalP$ by a polygon $mathcal{P}^{\prime }$ such that (1) $mathcal{P}^{\prime }$ contains $mathcalP$, (2) $mathcal{P}^{\prime }$ has its reflex vertices at the same positions as $mathcalP$, and (3) the number of vertices of $mathcal{P}^{\prime }$ 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 $mathcalP$ and $mathcal{P}^{\prime }$, 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 $mathcalP$.

Full work available at URL: https://arxiv.org/abs/1309.3858

Recommendations

• Geodesic-preserving polygon simplification
• Polygon simplification by minimizing convex corners
• Polygon simplification by minimizing convex corners
• Simplifying a polygonal subdivision while keeping it simple
• Progressive simplification of polygonal curves

zbMATH Keywords

geodesicshortest pathVoronoi diagrampolygonpolygonal domainsimple polygongeodesic hull

Mathematics Subject Classification ID

Data structures (68P05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cites Work

• \(L_ 1\) shortest paths among polygonal obstacles in the plane
• Triangulating a simple polygon in linear time
• Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
• An Optimal Algorithm for Euclidean Shortest Paths in the Plane
• Minimum-link paths revisited
• The furthest-site geodesic Voronoi diagram
• Optimal shortest path queries in a simple polygon
• A generalized Winternitz theorem
• Geodesic order types
• SEPARATING POINT SETS IN POLYGONAL ENVIRONMENTS
• Computing minimum length paths of a given homotopy class
• A new approach for the geodesic Voronoi diagram of points in a simple polygon and other restricted polygonal domains
• On minimum-area hulls
• Triangulations, visibility graph and reflex vertices of a simple polygon
• On-line construction of the convex hull of a simple polyline
• Allocating vertex \(\pi\)-guards in simple polygons via pseudo-triangulations
• Constructing pairwise disjoint paths with few links
• Extreme point and halving edge search in abstract order types

Cited In (8)

• Piercing pairwise intersecting geodesic disks
• Kinetic Geodesic Voronoi Diagrams in a Simple Polygon
• Title not available (Why is that?)
• Approximating the smallest \(k\)-enclosing geodesic disc in a simple polygon
• On simplifying shapes by subjecting them to collinearity constraints
• Shortcut hulls: vertex-restricted outer simplifications of polygons
• Plane geodesic spanning trees, Hamiltonian cycles, and perfect matchings in a simple polygon
• Polygon simplification by minimizing convex corners

This page was built for publication: Geodesic-preserving polygon simplification

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5261017)