Questions tagged [voronoi-diagrams]

For a given finite point set S, a voronoi diagram is a tessellation of a euclidean space. In the 2D case, it consists of conforming convex polygons surrounding each point such that for given a point p in S, any point in the enclosing polygon is closer to p than any other point in S.

Filter by
Sorted by
Tagged with
28
votes
5answers
18k views

Fastest Delaunay triangulation libraries for sets of 3D points

Which is the fastest library for performing delaunay triangulation of sets with millions if 3D points? Are there also GPU versions available? From the other side, having the voronoi tessellation of ...
9
votes
5answers
7k views

How are the Voronoi Tesselation and Delaunay triangulation problems duals of each other?

I have always been told that the Voronoi diagram is the dual of the Delaunay triangulation problem. In what sense can they be duals of each other? I thought that dual problems (i.e. in linear ...