Delaunay and Voronoi in 3D

Brad Barber bradb at
Thu Nov 29 18:07:48 PST 2001

At 09:57 AM 11/29/01, Balint MIKLOS wrote:
>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.

Yes, that is correct.

>  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.

A good, detailed introduction is Joseph O'Rourke's Computational Geometry
in C. Cambridge University Press.

>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 
>it would be great.

There are several code samples on the web for Voronoi diagrams.
You may find the Qhull 1.0 source useful (

I hope your project goes well.


>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

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