Divide-and-conquer for Voronoi diagrams revisited

DOI10.1016/j.comgeo.2010.04.004zbMath1207.05190OpenAlexW2148061022MaRDI QIDQ991182

Thomas Hackl, Wolfgang Aigner, Bert Jüttler, Margot Rabl, Franz Aurenhammer, Oswin Aichholzer, Elisabeth Pilgerstorfer

Publication date: 2 September 2010

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.comgeo.2010.04.004

zbMATH Keywords

Voronoi diagrammotion planningmedial axisdivide-and-conquerbiarc approximationtrimmed offset

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (3)

Efficient Voronoi diagram construction for planar freeform spiral curves ⋮ A competition flow method for computing medial axis transform ⋮ Mitered Offsets and Skeletons for Circular Arc Polygons

Uses Software

• VRONI

Cites Work

• Unnamed Item
• Unnamed Item
• Topology-oriented incremental computation of Voronoi diagrams of circular arcs and straight-line segments
• Randomized incremental construction of abstract Voronoi diagrams
• An O(n log n) algorithm for the Voronoi diagram of a set of simple curve segments
• A sweepline algorithm for Voronoi diagrams
• Concrete and abstract Voronoi diagrams
• Finding the medial axis of a simple polygon in linear time
• Spiral arc spline approximation to a planar spiral
• Pocket machining based on contour-parallel tool paths generated by means of proximity maps
• Voronoi diagrams and offset curves of curvilinear polygons.
• Mathematical theory of medial axis transform
• Approximating smooth planar curves by arc splines
• A compact piecewise-linear Voronoi diagram for convex sites in the plane
• The Voronoi diagram of curved objects
• Computational and Structural Advantages of Circular Boundary Representation
• Intersection and Closest-Pair Problems for a Set of Planar Discs
• Generalization of Voronoi Diagrams in the Plane
• Medial Axis Transformation of a Planar Shape
• The computational geometry algorithms library CGAL
• Divide-and-conquer for Voronoi diagrams revisited
• VRONI: An engineering approach to the reliable and efficient computation of Voronoi diagrams of points and line segments

This page was built for publication: Divide-and-conquer for Voronoi diagrams revisited