Divide-and-conquer for Voronoi diagrams revisited

DOI10.1016/J.COMGEO.2010.04.004MaRDI QIDQ991182zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

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

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

Describes a project that uses

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)