Divide-and-conquer for Voronoi diagrams revisited

DOI10.1016/J.COMGEO.2010.04.004zbMATH Open1207.05190OpenAlexW2148061022MaRDI QIDQ991182FDOQ991182

Authors: Oswin Aichholzer, Wolfgang Aigner, Franz Aurenhammer, T. Hackl, Bert Jüttler, Elisabeth Pilgerstorfer, Margot Rabl 

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

Recommendations

• Divide-and-conquer for Voronoi diagrams revisited
• scientific article; zbMATH DE number 403949
• Voronoi diagram and medial axis algorithm for planar domains with curved boundaries. I: Theoretical foundations
• Voronoi diagrams and offset curves of curvilinear polygons.
• scientific article; zbMATH DE number 4098181

zbMATH Keywords

motion planningVoronoi diagrammedial axisdivide-and-conquerbiarc approximationtrimmed offset

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (10)

• A modified DIviding RECTangles algorithm for a problem in astrophysics
• Interpolation by polygon rolling motions for approximate sweep computation
• 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
• Representing the Voronoï diagram of a simple polygon using rational quadratic Bézier curves
• The Voronoi diagram of planar convex objects
• Voronoi diagrams and offset curves of curvilinear polygons.
• The Voronoi diagram of curved objects
• Divide-and-conquer for Voronoi diagrams revisited

Uses Software

• VRONI

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

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