Dual planar graphs — click to add points, drag to move them
0
sites
0
triangles
0
Voronoi edges
2
V−E+F (Euler)
Voronoi diagram: V(p_i) = {x : d(x,p_i) ≤ d(x,p_j) for all j≠i}. Cells are convex polygons; each edge is equidistant from two sites. Delaunay triangulation: Dual graph of Voronoi. Characterized by the empty circumcircle property: no site lies inside any triangle's circumcircle. Duality: Voronoi vertices ↔ Delaunay triangles, Voronoi edges ↔ Delaunay edges. Maximizes the minimum angle over all triangulations. Euler's formula: V − E + F = 2 for connected planar graphs (including unbounded face).