Empty circle property
Triangle (a,b,c) in Delaunay iff no other point of P lies inside circumcircle. Equivalent to 'locally Delaunay' via edge flipping.
Advertisement
Fortune's algorithm
Sweep-line construction in O(N log N). Complex but standard.
Advertisement
Incremental
Add points one by one. Flip edges violating empty circle. Expected O(N log N).
Duality with Voronoi
Delaunay is dual of Voronoi diagram. Same information, different structure.