Delaunay and Voronoi in 3D

Balint MIKLOS mbalint at
Thu Nov 29 16:57:49 PST 2001

I would like to implement in Java an algorith to generate the Delaunay 
triangulation and the Voronoi cells for a set of points in 3D. I have read 
about an incremental agorithm, with the incircle test (for 2D), and the 
creation of the supertriangle at initialization. I suppose this algortihm can 
be adopted for 3D, with insphere test, and so on. I have read as well about 
data structures used, wich can be quadtree for 2D, and octree, N-tree for 3D, 
but I don't know what these are exactly, and how are they used. All I know is 
that, these trees make a distribution of the space.

Please help me, with a detaicled algorithm description, and how the data 
structures should be used. Since this computational geometry domain seems very 
interesting to me, I would like to ask, where I can start to study it. I have 
read Fukuda's FAQ about polyhedron and polytope structures and understood 
things, but if you could give me a detailed, and more explained book, or paper, 
it would be great.

I'm student at Technical Univerisity in Cluj-Napoca (2nd year), and couldn't 
find anything in our library. I couldn't get help from any professor at our 

Thank you in advance for your help!
Balint Miklos

Do you want a free e-mail for life ? Get it at

The compgeom mailing lists: see
or send mail to compgeom-request at with the line:
send readme
Now archived at

More information about the Compgeom-announce mailing list