# Incremental structure of a delaunay triangulation

This would probably be considered a reference request, as I would imagine it has been studied extensively in earlier work. Say I have a collection of distinct points $X = \{x_1,\dots,x_n\}$ in the plane and let $T_n$ denote their Delaunay triangulation. Suppose I consider the set of all possible Delaunay triangulations of the $n+1$ points $X\cup x$ for all $x\in\mathbb{R^2}$. What is the maximum number of such triangulations? Here I'm considering two triangulations to be equivalent if their edge sets are identical.

## 2 Answers

Assuming that no more than three of the points are on any circle with empty interior (which is the defining property of the Delaunay Triangulation of a planar pointset in general position), it seems reasonable to assume that the number of different triangulations that results from inserting a further point is equal to the number of open regions bounded by the empty circumcircles through 3 points.

The way, how inserting a further point affects the triangulation, depends on the number of the aforementioned empty circles, in which the inserted point lies.

The effects of inserting a point into a Delauny Triangulation are studied in algorithms for incremental construction of DT; if the added point lies in more than 1 circle, the defining property has to be restored by edge-flipping.

• The same as my answer :) – Igor Rivin Aug 14 '13 at 11:59
• @igor rivin: oops, you are right! So my credit, if any, is to have put it differently - maybe the two perspectives are interesting in itself. – Manfred Weis Aug 14 '13 at 15:42

I am not aware of a reference, and this is not quite an answer, as much as a recipe: Delaunay triangulations are better thought of as stereographic projections of convex polyhedra inscribed in the sphere (this is described quantitatively in my 1993 Annals paper, but was first observed qualitatively many years earlier -- computational geometers prefer projecting points on the paraboloid, for some reason). So, you are asking how many different polyhedra you get by adding a point (on the sphere, so outside the convex hull). The maximal number equals the number of regions in the partition of the sphere by the (continuations of) the faces of the polyhedron. I believe that this is equal to (at most) the number of edges plus the number of vertices, plus the number of edges of the original polyhedron, but I could be wrong.