Computing per-vertex (site) Voronoi cell areas directly from a Delaunay triangulation

Question

I wish to compute the areas of Voronoi cells which relate to a Delaunay triangulation of a point set without explicitly converting the Delaunay triangulation to a Voronoi graph. Since I only care about the areas of the Voronoi cells I wanted to avoid the cost of explicitly constructing the Voronoi data structure. Is this possible? Is there any relationship between the Delaunay triangulation/circles and the dual Voronoi cell areas? Thanks,

Philip

Answer 1

Using CGAL, a solution is provided here for the 3D case:

https://lists-sop.inria.fr/sympa/arc/cgal-discuss/2011-01/msg00117.html

Answer 2

You can use Shoelace formula once you know the vertices of the Voronoi cell in counter-clockwise order. This, however, is simple as the Delaunay triangulation is the dual of the Voronoi diagram: A Voronoi vertex is dual to a Delaunay triangle, and the vertex is located at the point equidistant to the triangle's corners.

So if you are interested in the area of the Voronoi cell of a point p in a pointset then (i) consider all incident Delaunay triangles T in counter-clockwise order, (ii) compute the loci of the Voronoi nodes, and (iii) plug in into Shoelace formula.