Wait, What? If you connect scattered points in the plane the right way, every triangle can certify itself with an empty circle.
That certificate defines the Delaunay triangulation. For a planar point set in general position, a Delaunay triangle has a circumcircle whose interior contains no other input point. This local geometric rule produces a globally useful structure connected to Voronoi diagrams, nearest-neighbour reasoning, mesh generation and computational geometry.
Quick Read
One-sentence answer: Delaunay triangulation algorithms build a planar triangulation satisfying the empty-circumcircle condition, commonly using incremental point insertion plus edge legalization, with robust orientation and in-circle predicates determining the combinatorial decisions.
- Beginner: understand triangulations, circumcircles and the empty-circle property.
- Intermediate: learn orientation tests, edge legality and local flips.
- Advanced: trace randomized incremental construction, point location and cavity-based insertion.
- Professional: handle degeneracies, adaptive-precision predicates, expected-complexity arguments, invariant testing and library-level engineering.
1. What Is a Triangulation?
Given a set of points in the plane, a triangulation connects them with non-crossing straight edges so that the convex hull is partitioned into triangles. Many triangulations may exist for the same point set.
Delaunay triangulation chooses a special one by imposing a geometric condition on those triangles.
2. The Empty-Circumcircle Property
Every non-collinear triangle has a unique circumcircle passing through its three vertices. A triangulation is Delaunay when the interior of every triangle’s circumcircle contains no other input point.
For point sets with no four cocircular points, this condition determines a unique Delaunay triangulation. Cocircular cases can admit more than one valid Delaunay triangulation, so tie-breaking and degeneracy policy matter.
3. Delaunay and Voronoi Are Dual Views
The Voronoi diagram partitions the plane into regions containing the points closest to each site. Two sites are connected by a Delaunay edge when their Voronoi regions share a boundary, subject to the usual degeneracy qualifications.
This duality is one reason Delaunay triangulations appear in spatial search, interpolation, meshing and geometric modelling: they encode neighbourhood structure without considering every pair of points.
4. Start With Orientation
The first fundamental predicate asks whether three points A, B and C make a left turn, right turn or are collinear. In coordinates, this is the sign of a 2×2 determinant derived from the vectors B−A and C−A.
Orientation tells an algorithm how triangles are wound, which side of an edge a point lies on and whether local topology is consistent. Do not build geometric data structures while treating orientation as an informal drawing judgement.
5. The In-Circle Predicate Is the Local Delaunay Test
Given an oriented triangle A, B, C and another point D, the in-circle predicate determines whether D lies inside, outside or on the circumcircle of ABC. Algebraically, this is the sign of a determinant whose interpretation depends on the orientation convention.
The predicate converts a geometric question into a discrete sign decision. That sign decides whether a local edge is legal.
6. Edge Legality and the Flip Idea
Consider two adjacent triangles sharing an interior edge. Together they form a quadrilateral when the local geometry is suitable. If the vertex opposite one triangle lies inside that triangle’s circumcircle, the shared edge violates the Delaunay condition. Replacing the diagonal with the other diagonal—an edge flip—can restore local legality.
This is powerful because a global triangulation property can be maintained through local tests and local topological changes.
7. Incremental Construction: Insert One Point at a Time
A natural algorithm starts with a triangulation containing all input points inside a large enclosing triangle or another suitable initial structure. Insert points one by one. For each new point, find where it belongs, update the local triangulation, then restore the Delaunay condition around the changed region.
The three jobs are therefore: locate, insert, legalize.
8. Point Location Is Not a Side Detail
If every insertion scans every triangle to find the containing face, the geometry may be correct but the algorithm will be unnecessarily slow. Efficient randomized incremental constructions maintain history or locality information so point location is fast in expectation.
This is a recurring algorithms lesson: the cost of finding where to perform a local update can dominate the update itself.
9. Random Order Makes the Analysis Work
Guibas, Knuth and Sharir developed a randomized incremental construction for planar Voronoi diagrams and Delaunay triangulations with expected O(n log n) time and O(n) space. The random insertion order prevents the algorithm from repeatedly encountering adversarial configurations that would make the history structure expensive.
Expected time here is over the algorithm’s random insertion order, not a claim that real-world point sets are randomly distributed.
10. One Incremental Style: Split and Legalize
If the new point lies strictly inside one triangle, split that triangle into three by connecting the point to the triangle’s vertices. The new edges are not automatically enough: neighbouring old edges may now fail the in-circle test.
Recursively or iteratively test affected edges. Flip any illegal edge and continue checking the new neighbourhood until every relevant local edge is legal.
11. Another Style: Bowyer–Watson Cavities
The Bowyer–Watson viewpoint identifies all current triangles whose circumcircles contain the inserted point. Those triangles form a cavity. Remove them, keep the cavity boundary, then connect the new point to the boundary to retriangulate the hole.
Edge-flip and cavity descriptions are closely related ways of understanding incremental Delaunay maintenance. For learning, trace both on the same five-point example and see that they enforce the same empty-circle invariant through different local narratives.
12. The Supertriangle Is Scaffolding, Not Output
Many simple implementations begin with a triangle large enough to contain all input points. This avoids special cases at the outer boundary during insertion. After all real points are inserted, remove every triangle incident to a supertriangle vertex.
A common bug is to forget that the supertriangle is algorithmic scaffolding and accidentally return it as part of the final geometry.
13. Floating-Point Arithmetic Can Break Topology
Orientation and in-circle tests often evaluate determinants whose true value may be extremely close to zero. Ordinary floating-point rounding can change the sign. One wrong sign can cause a wrong edge flip, inverted face, disconnected mesh or inconsistent triangulation.
Geometric robustness is therefore not merely about slightly inaccurate coordinates. A small numerical error can produce a qualitatively wrong combinatorial structure.
14. Robust Predicates: Spend Precision Only When Needed
Jonathan Shewchuk’s adaptive-precision orientation and in-circle predicates are a classic solution. Start with fast floating-point arithmetic and estimate whether the sign is trustworthy. If the result is too close to the error bound, increase precision until the sign can be determined correctly.
This adaptive strategy gives exact sign decisions for the predicate while avoiding expensive high precision on easy cases.
15. Degeneracies Need a Policy
- Duplicate points: decide whether to reject, merge or store multiplicity separately.
- Collinear points: a full 2D triangulation may not exist in the ordinary sense.
- Four or more cocircular points: multiple Delaunay triangulations may satisfy the empty-circle condition.
- Point on an existing edge: insertion changes a different local set of faces than strict interior insertion.
Robust predicates tell you that a degeneracy exists; they do not decide your application’s tie-breaking policy.
16. Library Engineering: Exact Predicates, Inexact Constructions
Professional computational-geometry libraries separate geometric predicates from constructions and often provide kernels with different exactness/performance trade-offs. CGAL’s Delaunay triangulation infrastructure, for example, represents the triangulation as a geometric data structure and relies on a traits/kernel layer for operations such as orientation and circumcircle tests.
The broader lesson is architectural: put numerical policy behind a clear predicate interface so the combinatorial algorithm does not contain ad hoc epsilon tests everywhere.
17. Common Failure States
- Checking whether triangle edges cross but never checking the Delaunay empty-circle condition.
- Using a fixed epsilon as a universal substitute for robust orientation and in-circle predicates.
- Forgetting that in-circle sign interpretation depends on triangle orientation.
- Assuming the Delaunay triangulation is always unique; cocircular points are a counterexample.
- Inserting points correctly but never legalizing neighbouring edges.
- Returning supertriangle faces in the final output.
- Claiming expected O(n log n) without stating the randomization and point-location assumptions.
- Testing only visually pleasant point clouds instead of nearly collinear and nearly cocircular cases.
18. Testing a Delaunay Implementation
Test both topology and geometry. Verify that every face is consistently oriented, every interior edge has exactly two incident triangles, boundary edges form the convex hull, faces do not cross and every local interior edge satisfies the Delaunay legality condition under a robust predicate.
For small point sets, compare against a trusted library. Generate random points, grids with perturbations, duplicate inputs, nearly collinear sets and points lying almost on existing circumcircles. Shuffle insertion order repeatedly: a correct implementation may return a different valid triangulation under degeneracy, but its invariant checks must still pass.
19. Practice Ladder: Beginner to Professional
- Level 1: draw several triangulations of five points and identify which edges differ.
- Level 2: construct a circumcircle and decide visually whether a fourth point is inside.
- Level 3: compute orientation signs and use them to keep every triangle consistently wound.
- Level 4: implement a simple in-circle test with exact integer arithmetic on small bounded coordinates.
- Level 5: insert one point into a triangulation and legalize edges by hand.
- Level 6: implement Bowyer–Watson with a brute-force scan for bad triangles.
- Level 7: add efficient point location or a history structure and randomize insertion order.
- Level 8: replace fragile floating-point signs with robust predicates and build property-based invariant tests.
20. How to Learn This Efficiently
Use pictures first, predicates second, data structures third. Predict whether an edge should flip by looking at a four-point configuration. Then compute the orientation and in-circle signs. Investigate what changes when one point moves across the circumcircle. Only after that should you implement the cavity or edge-legalization machinery.
Subgoal-labelled worked examples can separate “locate point,” “change local topology,” “test legality” and “repair neighbourhood.” PRIMM is especially natural here: predict the next flip, run a visual trace, investigate the predicate result, modify the point set, then make a triangulator. Parsons-style tasks can scaffold the insertion sequence before learners write geometry code from scratch.
21. Learning Hall Boundary
This article owns the public educational job of teaching Delaunay triangulation algorithms from first geometry through robust professional implementation. It does not take over broader geometry, spatial-index or learner-system jobs elsewhere in the eduKateSengkang estate. It does not redefine MindOS, Bolt or Student/Studying Interface, and it reveals no private eduKateAI prompts, routing, benchmarks, scoring or implementation details.
Sources and Further Reading
- Leonidas J. Guibas, Donald E. Knuth and Micha Sharir, Randomized Incremental Construction of Delaunay and Voronoi Diagrams, Algorithmica 7, 1992.
- CGAL, Delaunay_triangulation_2 documentation and 2D Triangulation package reference.
- Jonathan Richard Shewchuk, Adaptive Precision Floating-Point Arithmetic and Fast Robust Predicates for Computational Geometry, Discrete & Computational Geometry 18(3), 1997; see also the canonical robust-predicates implementation materials.
- Jean-Daniel Boissonnat, Olivier Devillers, Kunal Dutta and Marc Glisse, Randomized Incremental Construction of Delaunay Triangulations of Nice Point Sets, Discrete & Computational Geometry 66, 2021, DOI 10.1007/s00454-020-00235-7.
- ACM/IEEE-CS CS2023 guidance on algorithms, graphs, data structures, problem solving and testing.
- Sue Sentance, Jane Waite and Maria Kallia, PRIMM programming-education research, SIGCSE 2019, DOI 10.1145/3287324.3287477.
- Lauren E. Margulieux, Briana B. Morrison and Adrienne Decker, subgoal-labelled worked-example research, International Journal of STEM Education 7, 2020, DOI 10.1186/s40594-020-00222-7.
Professional rule: in computational geometry, protect combinatorial correctness with robust predicates; a nearly correct floating-point sign is still the wrong branch if it changes the topology.
eduKate Sengkang 