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).