Delaunay Triangulation and Voronoi Tessellations for Data Analysis

Approximately three years ago, when I first began exploring topological data analysis, I struggled to appreciate the advantages of the Delaunay complex over the Rips complex. I have noticed that within the TDA community, those with a stronger mathematical background tend to prefer Delaunay complexes over Rips complexes when working with data in $\mathbb{R}^d$ for $d \in \lbrace 1, 2, 3 \rbrace$. In contrast, people with an applied background such as statistics or data science, including myself, often find Rips complexes easier to grasp at first, and Delaunay complexes can feel too geometric or abstract to work with comfortably. In this post, I want to share my newfound appreciation for the Delaunay complex and Voronoi tessellations in data analysis. This blog assumes basic familiarity with Voronoi tessellations, Delaunay complexes and Alpha complexes. One of my earlier blogs titled “Simplicial Complexes” introduces some of the required basics. First section gives a more detailed introduction to Voronoi tessalations followed by a section focused on the mathematical duality connecting Delaunay and Voronoi complexes. The final section will focus on Alpha and Voronoi filtrations, along with an explanation on how to interpret these objects in the context of data analysis.

Voronoi tessellations

Voronoi tessellations are geometric objects that encode proximity information about a point set of interest. They are among the oldest geometric complexes to be studied and have been rediscovered at different times under different names, such as Dirichlet tessellations, Thiessen polygons, and Wigner–Seitz cells. However, the name Voronoi tessellations comes from the mathematician Georgy Voronoi, who studied the general $n$-dimensional case of this object. Some of the applications of Voronoi diagrams include crystal formation, meteorology, modelling animal territories and computational chemistry¹².

Let $S$ be a finite point set in $\mathbb{R}^d$. Then the Voronoi cell of a point $p \in S$, denoted by $\mathcal{V}(p)$, is defined as the set of all points in $\mathbb{R}^d$ that are closer to the point $p$ than any other point in $P \setminus \lbrace p \rbrace $.

\[\mathcal{V}(p) = \lbrace q \in \mathbb{R}^d \text{ } : \text{ } d(q, p) \leq d(q, p') \text{ for all } p' \in P \setminus \lbrace p \rbrace \rbrace\]

References