Finding the medial axis of a simple polygon in linear time

DOI10.1007/PL00009429zbMath0922.68128MaRDI QIDQ1289244

F. Chin, Jack Scott Snoeyink, Cao An Wang

Publication date: 27 May 1999

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

zbMATH Keywords

linear-time algorithm

Mathematics Subject Classification ID

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

Related Items

Packing two disks in a polygon ⋮ An almost optimal algorithm for Voronoi diagrams of non-disjoint line segments ⋮ Median trajectories ⋮ A Scheme for Computing Minimum Covers within Simple Regions ⋮ AN APPROXIMATE MORPHING BETWEEN POLYLINES ⋮ On selecting a fraction of leaves with disjoint neighborhoods in a plane tree ⋮ Realistic roofs over a rectilinear polygon ⋮ Exact and approximation algorithms for computing optimal fat decompositions ⋮ Packing two disks into a polygonal environment. ⋮ Deletion in abstract Voronoi diagrams in expected linear time and related problems ⋮ A scheme for computing minimum covers within simple regions ⋮ Optimal divisions of a convex body ⋮ Reachability by paths of bounded curvature in a convex polygon ⋮ Three problems about simple polygons ⋮ The snowblower problem ⋮ Tree-like decompositions of simply connected domains ⋮ COMPUTATIONAL AND STRUCTURAL ADVANTAGES OF CIRCULAR BOUNDARY REPRESENTATION ⋮ On the intersection graph of the disks with diameters the sides of a convex \(n\)-gon ⋮ Computing hereditary convex structures ⋮ On the estimation of the medial axis and inner parallel body ⋮ Analytical computation of arc menisci configuration under primary drainage in convex capillary cross sections ⋮ Divide-and-conquer for Voronoi diagrams revisited ⋮ Convexity-increasing morphs of planar graphs ⋮ Approximate convex decomposition of polygons ⋮ Conformal mapping in linear time ⋮ Delaunay triangulation of imprecise points in linear time after preprocessing ⋮ An iterated local search algorithm based on nonlinear programming for the irregular strip packing problem ⋮ Deletion in Abstract Voronoi Diagrams in Expected Linear Time. ⋮ Order-\(k\) \(\alpha\)-hulls and \(\alpha\)-shapes

This page was built for publication: Finding the medial axis of a simple polygon in linear time