The Delaunay triangulation of a point set is the triangulation where no point lies inside the circumcircle of any triangle. It is the dual graph of the Voronoi diagram. It maximizes the minimum angle across all possible triangulations, avoiding thin, degenerate triangles.
The circumcircle property
A triangulation is Delaunay if and only if for every triangle, the circumscribed circle contains no other points from the set. This "empty circle" property is the defining criterion. When it fails, you can fix it by flipping the shared edge of two adjacent triangles.
Scheme
; Check if point d is inside the circumcircle of triangle abc; Uses the determinant test (positive = inside for CCW triangles)
(define (in-circumcircle? ax ay bx by cx cy dx dy)
(let* ((adx (- ax dx)) (ady (- ay dy))
(bdx (- bx dx)) (bdy (- by dy))
(cdx (- cx dx)) (cdy (- cy dy))
(det (+ (* adx (- (* bdy (+ (* cdx cdx) (* cdy cdy)))
(* cdy (+ (* bdx bdx) (* bdy bdy)))))
(- (* ady (- (* bdx (+ (* cdx cdx) (* cdy cdy)))
(* cdx (+ (* bdx bdx) (* bdy bdy))))))
(* (+ (* adx adx) (* ady ady))
(- (* bdx cdy) (* bdy cdx))))))
(> det 0)))
; Triangle (0,0), (4,0), (2,3) — check if (2,1) is inside its circumcircle
(display "Point (2,1) inside circumcircle of triangle? ")
(display (in-circumcircle? 00402321)) (newline)
; Point far away should be outside
(display "Point (10,10) inside circumcircle? ")
(display (in-circumcircle? 0040231010))
Python
def in_circumcircle(ax, ay, bx, by, cx, cy, dx, dy):
"""Returns True if (dx,dy) is inside circumcircle of (a,b,c) in CCW order."""
adx, ady = ax - dx, ay - dy
bdx, bdy = bx - dx, by - dy
cdx, cdy = cx - dx, cy - dy
det = (adx * (bdy * (cdx**2 + cdy**2) - cdy * (bdx**2 + bdy**2))
- ady * (bdx * (cdx**2 + cdy**2) - cdx * (bdx**2 + bdy**2))
+ (adx**2 + ady**2) * (bdx * cdy - bdy * cdx))
return det > 0print(f"(2,1) inside circumcircle? {in_circumcircle(0,0, 4,0, 2,3, 2,1)}")
print(f"(10,10) inside circumcircle? {in_circumcircle(0,0, 4,0, 2,3, 10,10)}")
Maximizes minimum angle
Among all triangulations of the same point set, the Delaunay triangulation has the largest minimum angle. This makes it ideal for finite element methods, terrain modeling, and mesh generation, where skinny triangles cause numerical instability.
Scheme
; Compute angles of a triangle from its vertices; Uses the law of cosines: cos(C) = (a^2 + b^2 - c^2) / (2ab)
(define pi 3.141592653589793)
(define (dist-sq p q)
(+ (* (- (car p) (car q)) (- (car p) (car q)))
(* (- (cadr p) (cadr q)) (- (cadr p) (cadr q)))))
(define (angle-at a b c)
; Angle at vertex a, opposite side bc
(let* ((ab2 (dist-sq a b))
(ac2 (dist-sq a c))
(bc2 (dist-sq b c))
(cos-a (/ (+ ab2 ac2 (- bc2))
(* 2 (sqrt ab2) (sqrt ac2)))))
(* (/ 180 pi) (acos (max -1 (min 1 cos-a))))))
(define (min-angle a b c)
(min (angle-at a b c) (angle-at b a c) (angle-at c a b)))
; Good triangle (Delaunay-like): equilateral-ish
(define t1-a (list 00)) (define t1-b (list 40)) (define t1-c (list 23))
(display "Good triangle min angle: ")
(display (min-angle t1-a t1-b t1-c)) (newline)
; Bad triangle (skinny): nearly degenerate
(define t2-a (list 00)) (define t2-b (list 100)) (define t2-c (list 50.5))
(display "Skinny triangle min angle: ")
(display (min-angle t2-a t2-b t2-c)) (newline)
(display "Delaunay avoids skinny triangles.")
The dual of Voronoi
Connect two sites with an edge whenever their Voronoi cells share a boundary. The result is the Delaunay triangulation. Every Voronoi vertex (where three cells meet) becomes a Delaunay triangle. Every Voronoi edge (between two cells) becomes a Delaunay edge. The two structures encode the same spatial information from dual perspectives.
Convex hull in one higher dimension
A remarkable connection: lift each 2D point (x, y) to 3D as (x, y, x² + y²), placing it on a paraboloid. The lower convex hull of these lifted points, projected back to 2D, gives the Delaunay triangulation. This means any convex hull algorithm in (d+1) dimensions gives you a Delaunay triangulation in d dimensions for free.
Scheme
; Lifting trick: 2D point (x,y) -> 3D point (x, y, x^2 + y^2); The Delaunay triangulation in 2D = lower convex hull in 3D
(define (lift-to-paraboloid p)
(let ((x (car p)) (y (cadr p)))
(list x y (+ (* x x) (* y y)))))
(define points (list (list 00) (list 30) (list 12) (list 43)))
(display "Original 2D points:") (newline)
(for-each (lambda (p) (display " ") (display p) (newline)) points)
(display "Lifted to paraboloid:") (newline)
(for-each (lambda (p)
(display " ") (display (lift-to-paraboloid p)) (newline))
points)
(display "Lower convex hull of lifted points") (newline)
(display "projected back to 2D = Delaunay triangulation")
The in-circumcircle test uses a 4x4 determinant reduced to a 3x3 form. The sign convention assumes counter-clockwise vertex ordering; swap any two vertices and the sign flips. The lifting-to-paraboloid construction is exact: the lower convex hull facets in 3D correspond bijectively to Delaunay triangles in 2D. This is the basis of the fastest known Delaunay algorithms (via 3D convex hull in expected O(n log n)).
Delaunay triangulation) · CC BY-SA 4.0