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.68162OpenAlexW2018168260MaRDI QIDQ5943290

Martin Held

Publication date: 27 September 2001

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

Full work available at URL: https://doi.org/10.1016/s0925-7721(01)00003-7

zbMATH Keywords

Voronoi diagrams

Mathematics Subject Classification ID

Computing methodologies for image processing (68U10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items (12)

Representation of segment Voronoi diagram by Bézier curves ⋮ Optimizing the geometrical accuracy of curvilinear meshes ⋮ A FAST STRAIGHT-SKELETON ALGORITHM BASED ON GENERALIZED MOTORCYCLE GRAPHS ⋮ TOPOLOGY-PRESERVING WATERMARKING OF VECTOR GRAPHICS ⋮ Automatic piloting in progressive dies using medial axis transform ⋮ BIARC APPROXIMATION, SIMPLIFICATION AND SMOOTHING OF POLYGONAL CURVES BY MEANS OF VORONOI-BASED TOLERANCE BANDS ⋮ Exact Voronoi diagram of smooth convex pseudo-circles: general predicates, and implementation for ellipses ⋮ Analytical computation of arc menisci configuration under primary drainage in convex capillary cross sections ⋮ Divide-and-conquer for Voronoi diagrams revisited ⋮ A Methodology for Automated Cartographic Data Input, Drawing and Editing Using Kinetic Delaunay/Voronoi Diagrams ⋮ VRONI ⋮ Topology-Oriented Incremental Algorithm for the Robust Construction of the Voronoi Diagrams of Disks

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

This page was built for publication: VRONI: An engineering approach to the reliable and efficient computation of Voronoi diagrams of points and line segments