The Delaunay Triangulation Maximizes the Mean Inradius.
Timothy D. Lambert · 1994
I prove that amongst all triangulations of a planar point set the Delaunay triangulation maximizes the arithmetic mean of the inradii of the triangles. 1 Introduction A triangulation of a set of points is a partition of the convex hull into triangles. The Delaunay triangulation is a well known triangulation, being the planar dual of the famous Voronoi diagram. Most applications of triangulations require that the triangulation should avoid `skinny' triangles. Many different measures of the skinniness of a triangle have been proposed. One of these is the inradius (radius of the inscribed circle) [14, 19]. In this paper I prove that the Delaunay triangulation is the triangulation that maximizes the arithmetic mean of the inradius. 1.1 Background Triangulating sets of points is a very important problem in computational geometry; there are far too many applications in computational geometry and other fields to mention here. (See the surveys [4, 6, 1]) There are many different possible ...