CGAL users discussion list

[Laurent Rineau <>]

On Friday 03 October 2008 17:21:42 

 wrote:
> > thus the complexity is exactly the same (since it is the same stuff)
>
> I think he means "difficulty" in implementing, not actual complexity. In
> this case, Delaunay seems to be the choice in CGAL, and I see it easier to
> implement myself. Thanks to the empty circle condition, I would had some
> idea about how to introduce new points, and re-triangulate; for the
> Voronoi, the thing seems much more delicate. It is true that many textbooks
> talk about just everything but often fail to mention ease of implementation
> and applicability.

For the euclidean distance, and with points in general position, computing a 
Voronoi diagram and computing a Delaunay triangulation is exactly the same: 
same result and same algorithm. The only difference is that for Voronoi you 
need to compute Voronoi vertices (which are circumcenters).

-- 
Laurent Rineau, PhD
Engineer at GeometryFactory
http://www.geometryfactory.com/