Shortcut hulls: vertex-restricted outer simplifications of polygons

DOI10.1016/J.COMGEO.2023.101983MaRDI QIDQ6103172zbMATH OpenOpenAlexFDO

Authors Annika Bonerath, Jan-Henrik Haunert, Joseph S. B. Mitchell, Benjamin Niedermann

Publication date 26 June 2023

Published in Computational Geometry (Search for Journal in Brave)

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

zbMATH Keywords

dynamic programminggeographical information sciencepolygon simplification

Mathematics Subject Classification ID

Computational aspects related to convexity (52B55) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: Let $P$ be a crossing-free polygon and $mathcalC$ a set of shortcuts, where each shortcut is a directed straight-line segment connecting two vertices of $P$. A shortcut hull of $P$ is another crossing-free polygon that encloses $P$ and whose oriented boundary is composed of elements from $mathcalC$. Shortcut hulls find their application in geo-related problems such as the simplification of contour lines. We aim at a shortcut hull that linearly balances the enclosed area and perimeter. If no holes in the shortcut hull are allowed, the problem admits a straight-forward solution via shortest paths. For the more challenging case that the shortcut hull may contain holes, we present a polynomial-time algorithm that is based on computing a constrained, weighted triangulation of the input polygon's exterior. We use this problem as a starting point for investigating further variants, e.g., restricting the number of edges or bends. We demonstrate that shortcut hulls can be used for drawing the rough extent of point sets as well as for the schematization of polygons.

Recommendations

• Progressive simplification of polygonal curves
• Geodesic-preserving polygon simplification
• Simplifying a polygonal subdivision while keeping it simple
• Geodesic-preserving polygon simplification

Cites work

• Area-preserving subdivision simplification with topology constraints: exactly and in practice
• Constrained Delaunay triangulations
• Efficient computation of minimum-area rectilinear convex hull under rotation and generalizations
• Efficient generation of simple polygons for characterizing the shape of a set of points in the plane
• Fast segment insertion and incremental construction of constrained Delaunay triangulations
• Finding the Constrained Delaunay Triangulation and Constrained Voronoi Diagram of a Simple Polygon in Linear Time
• Generalized Delaunay triangulation for planar graphs
• Geodesic-preserving polygon simplification
• Homotopic \(\mathcal{C}\)-oriented routing with few links and thick edges
• scientific article; zbMATH DE number 2185597 (Why is no real title available?)
• Introduction to algorithms.
• Jaywalking your dog: computing the Fréchet distance with shortcuts
• MINIMUM-LINK C-ORIENTED PATHS: SINGLE-SOURCE QUERIES
• Minimum-link paths revisited
• On the shape of a set of points in the plane
• Optimal computation of finitely oriented convex hulls
• Rectilinear paths among rectilinear obstacles
• Restricted-orientation convexity.
• Scalable exact visualization of isocontours in road networks via minimum-link paths
• Simplifying a polygonal subdivision while keeping it simple
• Streaming algorithms for line simplification
• Triangulating a simple polygon
• Triangulating a simple polygon in linear time
• TRIANGULATING DISJOINT JORDAN CHAINS

Cited in

(1)

• Efficient computation of crossing components and shortcut hulls

This page was built for publication: Shortcut hulls: vertex-restricted outer simplifications of polygons

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