Optimality of the delaunay triangulation in ℝ^d

Abstract

In this paper we present an optimality result for the Delaunay triangulation of a set of points in ℝd. We also show that some of the well known properties of the Delaunay triangulation in ℝ2 can, when appropriately denned, be generalized to the Delaunay triangulation in ℝd. In particular, we show that (a) the maximum min-containment radius (the radius of the smallest sphere containing the simplex) of the Delaunay triangulation of a point set in ℝd is less than the maximum min-containment radius of any other triangulation of the point set, (b) if a valid triangulation consists of only self-centered triangles (a simplex whose circumcenter falls inside the simplex) then it is the Delaunay triangulation, and (c) there exists an incremental flip algorithm (one that modifies the triangulation locally to make it Delaunay) that can generate the Delaunay triangulation for any point set. We further show that the Delaunay triangulation can be seen as the optimum solution to a continuum optimization problem.