VRONI: An engineering approach to the reliable and efficient computation of Voronoi diagrams of points and line segments

DOI10.1016/S0925-7721(01)00003-7zbMath0976.68162MaRDI QIDQ5943290

Martin Held

Publication date: 27 September 2001

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

zbMATH Keywords

Voronoi diagrams

Mathematics Subject Classification ID

68U10: Computing methodologies for image processing

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

Related Items

VRONI, Automatic piloting in progressive dies using medial axis transform, Divide-and-conquer for Voronoi diagrams revisited, Analytical computation of arc menisci configuration under primary drainage in convex capillary cross sections, BIARC APPROXIMATION, SIMPLIFICATION AND SMOOTHING OF POLYGONAL CURVES BY MEANS OF VORONOI-BASED TOLERANCE BANDS, A Methodology for Automated Cartographic Data Input, Drawing and Editing Using Kinetic Delaunay/Voronoi Diagrams

Uses Software

• LEDA
• Triangle
• FIST
• Voronoi

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A linear-time algorithm for computing the Voronoi diagram of a convex polygon
• An O(n log n) algorithm for the Voronoi diagram of a set of simple curve segments
• A sweepline algorithm for Voronoi diagrams
• An automatic coarse and fine surface mesh generation scheme based on medial axis transform. I: Algorithms
• On the computational geometry of pocket machining
• Pocket machining based on contour-parallel tool paths generated by means of proximity maps
• Voronoi diagrams and offset curves of curvilinear polygons.
• Surface reconstruction by Voronoi filtering
• Special issue: Implementation of geometric algorithms
• Topology-oriented implementation -- an approach to robust geometric algorithms
• Efficient exact evaluation of signs of determinants
• Shortest path geometric rounding
• IMPROVEMENTS OF THE INCREMENTAL METHOD FOR THE VORONOI DIAGRAM WITH COMPUTATIONAL COMPARISON OF VARIOUS ALGORITHMS
• Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms
• Generalization of Voronoi Diagrams in the Plane
• Medial Axis Transformation of a Planar Shape
• A straightforward algorithm for computing the medial axis of a simple polygon
• RANDOMIZATION YIELDS SIMPLE O(n log^⋆ n) ALGORITHMS FOR DIFFICULT Ω(n) PROBLEMS
• Robust Proximity Queries: An Illustration of Degree-Driven Algorithm Design
• FIST: fast industrial-strength triangulation of polygons