Finding the medial axis of a simple polygon in linear time

DOI10.1007/BFB0015444MaRDI QIDQ6487986zbMATH OpenFDO

Authors Francis Y. L. Chin, Jack Snoeyink, Cao An Wang

Publication date 21 March 2023

Full work available at URL https://doi.org/10.1007/BFB0015444

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Nonnumerical algorithms (68W05) Analysis of algorithms (68W40)

Recommendations

• Finding the medial axis of a simple polygon in linear time
• A straightforward algorithm for computing the medial axis of a simple polygon
• Triangulating a simple polygon in linear time
• An algorithm for determining the medial axis of an arbitrary simple polygon
• On triangulation axes of polygons

Cites work

• A linear-time algorithm for computing the Voronoi diagram of a convex polygon
• An automatic coarse and fine surface mesh generation scheme based on medial axis transform. I: Algorithms
• Axial representations of shape
• scientific article; zbMATH DE number 177538 (Why is no real title available?)
• scientific article; zbMATH DE number 1079755 (Why is no real title available?)
• scientific article; zbMATH DE number 3436645 (Why is no real title available?)
• Medial Axis Transformation of a Planar Shape
• On the computational geometry of pocket machining
• RANDOMIZATION YIELDS SIMPLE O(n log^⋆ n) ALGORITHMS FOR DIFFICULT Ω(n) PROBLEMS
• Triangulating a simple polygon in linear time

Cited in

(11)

• Finding the medial axis of a simple polygon in linear time
• On fat partitioning, fat covering and the union size of polygons
• Approximation algorithms for lawn mowing and milling
• A fully general, exact algorithm for nesting irregular shapes
• An algorithm for determining the medial axis of an arbitrary simple polygon
• scientific article; zbMATH DE number 1194033 (Why is no real title available?)
• A straightforward algorithm for computing the medial axis of a simple polygon
• Linear-time heuristics for minimum weight rectangulation
• VRONI: An engineering approach to the reliable and efficient computation of Voronoi diagrams of points and line segments
• Asynchronous deterministic rendezvous in bounded terrains
• Compatible connectivity augmentation of planar disconnected graphs

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

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