Stability of Delaunay Triangulations Under Perturbation

20 concepts10 papers1 proposal

Delaunay triangulations are a cornerstone of computational geometry, prized for their ability to maximize the minimum angle of triangles in a mesh. This property makes them ideal for physics simulations, surface reconstruction, and geometric modeling. However, standard Delaunay triangulations suffer from a fatal flaw: they are notoriously sensitive to small changes. A microscopic shift in a vertex's position or a slight warp in the underlying distance metric can trigger a cascade of edge flips, fundamentally altering the topology of the mesh.

In practical applications, this fragility introduces severe numerical instability. If a simulation slightly deforms a mesh, or if a surface simplification algorithm compresses a shape, the resulting topological churn can break downstream partial differential equation (PDE) solvers, as noted by Hsueh-Ti Derek Liu et al.. To build robust geometric pipelines, we must understand not just what a Delaunay triangulation is, but why it breaks, and how we can mathematically guarantee its stability under perturbation.

The Root of Instability: Circumcenter Drift

To understand why Delaunay triangulations flip, we must look at their defining geometric feature: the empty circumcircle criterion. A triangulation is Delaunay if the circumsphere of every simplex contains no other points from the dataset.

When a vertex moves, its simplex's circumsphere changes. If the simplex is well-shaped (like an equilateral triangle), a small movement of a vertex causes a correspondingly small shift in its circumcenter. The circumsphere remains stable, and neighboring points stay safely outside.

   Stable (Thick) Simplex                 Unstable (Sliver) Simplex
          ▲                                         ▲
         / \                                       / \
        /   \   (Small circumcenter               /   \   (Massive circumcenter
       /  •  \   displacement)                   /_____\   displacement)
      /_______\                                     •

However, consider a "sliver"—a nearly flat, degenerate simplex whose vertices are almost co-linear or co-planar. The circumcircle of a sliver is massive, and its circumcenter sits far outside the simplex itself. Because the vertices are nearly flat, a tiny nudge to one vertex can cause the circumcenter to violently swing across space, radically expanding or shrinking the circumcircle. If another point happens to reside near the boundary of this ballooning sphere, the empty-circle criterion is instantly violated, forcing a topological edge flip.

Jean-Daniel Boissonnat et al. formalized this intuition by proving a direct mathematical relationship between a simplex's shape and its sensitivity to change. They demonstrated that the displacement of a simplex's circumcenter under perturbation is inversely proportional to its thickness (a geometric invariant measuring how far a simplex is from being flat). Thick simplices anchor their circumcenters securely in place, making them robust against both point displacements and variations in the underlying geometric metric.

Quantifying Robustness via Protection and d-Genericity

If thickness protects an isolated simplex, how do we protect an entire triangulation? The answer lies in two related concepts: protection and $d$-genericity.

A triangulation is considered "protected" if its empty circumspheres aren't just empty, but have a buffer zone. As explored by Aruni Choudhary et al., protection can be quantified by a circumball inflation metric: how much can you expand a simplex's circumsphere before it hits an external point? If every circumsphere can expand significantly, the mesh is far from numerical degeneracy.

              Protected Simplex                     Unprotected Simplex

                 .

-  -  .                            .
-  -  .
               '     ▲      '                        '     ▲      '
              '     / \      '                      '     / \      '
             '     /   \      '                    '     /   \  ●   ' <--- External point
             '    /  •  \     '                    '    /  •  \     '      dangerously close
              '  /_______\   '                      '  /_______\   '
               '            '                        '            '
                 '  -  -  '                            '  -  -  '
              [Large Buffer Zone]                    [No Buffer Zone]

When a point set is structured such that all its simplices are well-separated from degenerate states, the point set is said to be $d$-generic. Achieving $d$-genericity provides a theoretical shield. Jean-Daniel Boissonnat et al. showed that by applying an iterative, controlled perturbation to any given point set, one can force the system into a $d$-generic configuration. This process guarantees that all resulting simplices possess bounded thickness and high protection, rendering the global Delaunay topology immune to minor metric or position shifts.

Maintaining Stability in Dynamic Settings

In many real-world applications, points are not static; they move continuously over time. Recomputing the full Delaunay triangulation at every time step is computationally prohibitive and introduces constant topological flickering. Researchers handle this dynamic challenge using two distinct strategies: safe zones and stable subgraphs.

Safe Zones via Bi-Cell Filtering

Instead of checking the entire mesh, we can look at local pairs of adjacent simplices, known as bi-cells. Yuanfeng Zhou et al. developed a mathematical criterion derived from matrix determinants to calculate "safe zones" for these bi-cells. If the vertices move within their designated safe zones, the underlying matrix properties guarantee that the local Delaunay property cannot be violated. This allows algorithms to bypass unnecessary updates entirely, filtering out the vast majority of static computations.

Stable Delaunay Graphs (SDGs)

If the full Delaunay triangulation is simply too volatile under motion, an alternative is to track only the edges that are fundamentally robust. Pankaj K. Agarwal et al. introduced the Stable Delaunay Graph (SDG), which is a dynamic subgraph of the standard Delaunay triangulation.

The core mechanism relies on evaluating Delaunay properties under alternative geometric frameworks, such as polygonal norms, which exhibit higher intrinsic stability. By filtering out the hyper-sensitive edges that flip back and forth constantly, the authors proved that the SDG experiences significantly fewer topological changes while still retaining the essential geometric connectivity required for accurate spatial tracking.

Generalizing Beyond Flat Euclidean Space

The insights gained from studying thickness and protection in flat Euclidean space turn out to be universal geometric principles. They provide the mathematical foundation for solving complex problems across diverse domains:

  • Manifold Triangulation: Triangulating curved, non-Euclidean spaces is notoriously difficult because the metric changes depending on where you are on the surface. By adapting Euclidean perturbation strategies to curved settings, Jean-Daniel Boissonnat et al. developed the first algorithm guaranteed to produce a stable Delaunay triangulation for any compact Riemannian manifold.
  • Shape Analysis: When analyzing shapes or point clouds subjected to noise and distortion, tracking exact discretizations fails. Ruqi Huang et al. overcame this by bounding perturbations simultaneously in both the shape's metric geometry and its measure sampling density, allowing functional operators to remain stable without relying on a fixed mesh.
  • Neural Network Parameterization: Deep ReLU networks represent continuous piecewise-linear (CPWL) functions, which can be viewed as functions defined over irregular triangulations. This parameterization is often highly unstable. Alexis Goujon et al. proved that the stability of these representations is governed by the "star volume" of each vertex (the total volume of all simplices meeting at that vertex). Bounding the ratio of these volumes guarantees a stable, well-conditioned function mapping.

Ultimately, whether compressing a 3D mesh for a physics engine or training a neural network, ensuring stability requires moving away from fragile, exact geometric thresholds. By optimizing for thickness, enforcing $d$-genericity, and carving out mathematical safe zones, we can transform Delaunay triangulations from brittle abstractions into resilient structures capable of weathering real-world noise and motion.

Key Foundational Work

The stability of Delaunay Triangulations (2013) — contributed 9 concept elements to this direction.
Delaunay Triangulation of Manifolds (2013) — contributed 2 concept elements to this direction.
Fast Updating of Delaunay Triangulation of Moving Points by Bi-cell Filtering (2010) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_d_genericity_d4d601a4,
  title = {d-genericity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/d-genericity/rdr_d4d601a467164587993882519d123e96},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_d_genericity_d4d601a4_v1,
  title = {d-genericity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/d-genericity/rdr_d4d601a467164587993882519d123e96/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake