Paper Info
Title
Computing the 3D Voronoi Diagram Robustly: An Easy Explanation
Abstract
Many algorithms exist for computing the 3D Voronoi diagram, but in most cases they assume that the input is in general position. Because of the many degeneracies that arise in 3D geometric computing, their implementation is still problematic in practice. In this paper, I describe a simple 3D Voronoi diagram (and Delaunay tetrahedralization) algorithm, and I explain, by giving as many details and insights as possible, how to ensure that it outputs a correct structure, regardless of the spatial distribution of the points in the input.
Year
DOI
Venue
2007
10.1109/ISVD.2007.10
ISVD
Keywords
Field
DocType
delaunay tetrahedralization,spatial distribution,voronoi diagram robustly,correct structure,easy explanation,general position,voronoi diagram,geometric computing,geographic information systems,data mining,data structures,computational geometry,distributed computing,sorting,robustness,algorithm design and analysis,application software
General position,Centroidal Voronoi tessellation,Bowyer–Watson algorithm,Computer science,Computational geometry,Theoretical computer science,Geometric computing,Voronoi diagram,Delaunay triangulation
Conference
ISBN
Citations 
PageRank 
0-7695-2869-4
7
0.63
References 
Authors
28
1
Name
Order
Citations
PageRank
Hugo Ledoux123122.27