[PDF][PDF] Optimality of the Delaunay triangulation in Rd
VT Rajan - Proceedings of the seventh annual symposium on …, 1991 - dl.acm.org
Proceedings of the seventh annual symposium on Computational geometry, 1991•dl.acm.org
In this paper we present an optimality result for the Delaunay triangulation of a set of points
in Etd. We also show that some of the well known properties of the Delaunay triangulation in
IR2 can, when appropriately defined, be generalized to the Delaunay triangulation in Etd. In
particular, we show that (a) the maximum rein-containment radius (the radius of the smallest
sphere containing the simplex of the 1 Delaunay triangulation of a point set in Et is less than
the maximum rein-containment radius of any other triangulation of the point set,(b) if a valid …
in Etd. We also show that some of the well known properties of the Delaunay triangulation in
IR2 can, when appropriately defined, be generalized to the Delaunay triangulation in Etd. In
particular, we show that (a) the maximum rein-containment radius (the radius of the smallest
sphere containing the simplex of the 1 Delaunay triangulation of a point set in Et is less than
the maximum rein-containment radius of any other triangulation of the point set,(b) if a valid …
Abstract
In this paper we present an optimality result for the Delaunay triangulation of a set of points in Etd. We also show that some of the well known properties of the Delaunay triangulation in IR2 can, when appropriately defined, be generalized to the Delaunay triangulation in Etd. In particular, we show that (a) the maximum rein-containment radius (the radius of the smallest sphere containing the simplex of the 1 Delaunay triangulation of a point set in Et is less than the maximum rein-containment radius of any other triangulation of the point set,(b) if a valid triangulation consists of only self-centered triangles(a simplex whose circumventer 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.