Computing the 3D Voronoi Diagram Robustly: An Easy Explanation

	This Article
	Subscribers, please Login Purchase article: $19 PDF IEEE Xplore Subscribers RSS feed
	Share
	Email this Article to a friend
	Bibliographic References
	ASCII Text BibTex RefWorks Procite/RefMan/Endnote
	Add to:
	Digg Furl Spurl Blink Simpy Google Del.icio.us Y!MyWeb
	Search
	Similar Articles Articles by Hugo Ledoux

4th International Symposium on Voronoi Diagrams in Science and Engineering (ISVD 2007)

University of Glamorgan, Pontypridd, Wales

July 09-July 11

ISBN: 0-7695-2869-4

	ASCII Text	x
	Hugo Ledoux, "Computing the 3D Voronoi Diagram Robustly: An Easy Explanation," International Symposium on Voronoi Diagrams in Science and Engineering, pp. 117-129, 4th International Symposium on Voronoi Diagrams in Science and Engineering (ISVD 2007), 2007.

	BibTex	x
	@article{ 10.1109/ISVD.2007.10, author = {Hugo Ledoux}, title = {Computing the 3D Voronoi Diagram Robustly: An Easy Explanation}, journal ={International Symposium on Voronoi Diagrams in Science and Engineering}, volume = {0}, year = {2007}, isbn = {0-7695-2869-4}, pages = {117-129}, doi = {http://doi.ieeecomputersociety.org/10.1109/ISVD.2007.10}, publisher = {IEEE Computer Society}, address = {Los Alamitos, CA, USA}, }

	RefWorks Procite/RefMan/Endnote	x
	TY - CONF JO - International Symposium on Voronoi Diagrams in Science and Engineering TI - Computing the 3D Voronoi Diagram Robustly: An Easy Explanation SN - 0-7695-2869-4 SP117 EP129 A1 - Hugo Ledoux, PY - 2007 KW - null VL - 0 JA - International Symposium on Voronoi Diagrams in Science and Engineering ER -

Hugo Ledoux, Delft University of Technology, the Netherlands

DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ISVD.2007.10

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.

Citation:

Hugo Ledoux, "Computing the 3D Voronoi Diagram Robustly: An Easy Explanation," isvd, pp.117-129, 4th International Symposium on Voronoi Diagrams in Science and Engineering (ISVD 2007), 2007

Peer Review Notice | Give Us Feedback

Usage of this product signifies your acceptance of the Terms of Use.