APPROXIMATING POLYGONS AND SUBDIVISIONS WITH MINIMUM-LINK PATHS

DOI10.1142/S0218195993000257zbMath0803.68134OpenAlexW2172137407MaRDI QIDQ4289634

Jack Scott Snoeyink, Joseph S. B. Mitchell, J. E. Hershberger, Leonidas J. Guibas

Publication date: 2 January 1995

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

Full work available at URL: https://doi.org/10.1142/s0218195993000257

zbMATH Keywords

polygonal approximationcurve segmentationFréchet metriccartographic line simplificationlink metric

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items (33)

A graph theoretical approach to the firebreak locating problem ⋮ Structured discrete shape approximation: theoretical complexity and practical algorithm ⋮ Touring a sequence of disjoint polygons: complexity and extension ⋮ Constructing pairwise disjoint paths with few links ⋮ Roman domination in subgraphs of grids ⋮ Separation and approximation of polyhedral objects ⋮ KINETIC COLLISION DETECTION FOR SIMPLE POLYGONS ⋮ SPACE-EFFICIENT ALGORITHMS FOR APPROXIMATING POLYGONAL CURVES IN TWO-DIMENSIONAL SPACE ⋮ Area-preserving approximations of polygonal paths ⋮ Fitting a two-joint orthogonal chain to a point set ⋮ On the computational complexity of Roman\(\{2\}\)-domination in grid graphs ⋮ Fréchet Distance for Uncertain Curves ⋮ Minimum-link \(C\)-oriented paths visiting a sequence of regions in the plane ⋮ Route-enabling graph orientation problems ⋮ Efficient observer-dependent simplification in polygonal domains ⋮ Continuous location of dimensional structures. ⋮ Approximation of an open polygonal curve with a minimum number of circular arcs and biarcs ⋮ Stabbing segments with rectilinear objects ⋮ Computing homotopic line simplification ⋮ Place the Vertices Anywhere on the Curve and Simplify ⋮ An optimal algorithm for minimum-link rectilinear paths in triangulated rectilinear domains ⋮ Polygonal chain approximation: A query based approach ⋮ Optimization for first order Delaunay triangulations ⋮ Polygon simplification by minimizing convex corners ⋮ Unnamed Item ⋮ An O(n log n) ALGORITHM FOR FINDING A SHORTEST CENTRAL LINK SEGMENT ⋮ Simplifying 3D Polygonal Chains Under the Discrete Fréchet Distance ⋮ Global Curve Simplification ⋮ Streaming algorithms for line simplification ⋮ Edges and switches, tunnels and bridges ⋮ On Optimal Polyline Simplification Using the Hausdorff and Fréchet Distance ⋮ Polygonal path simplification with angle constraints ⋮ New limits of treewidth-based tractability in optimization

This page was built for publication: APPROXIMATING POLYGONS AND SUBDIVISIONS WITH MINIMUM-LINK PATHS