You are an expert at summarizing long articles. Proceed to summarize the following text: 
the _ voronoi diagram _ of points @xmath0 in @xmath1-dimensional euclidean space decomposes @xmath2 into @xmath3 convex polyhedra , called _ voronoi domains_. the domain of @xmath4 is the set of points @xmath5 for which @xmath4 minimizes the euclidean distance : @xmath6 for points in general position , the geometrically realized nerve ( the straight - line dual in @xmath7 ) decomposes the convex hull of the points into simplices , called the _ delaunay triangulation_. it is a particular _ geometric triangulation _ of the points , which is a simplicial complex whose vertices are the given points and whose underlying space is convex . delaunay triangulations are used in numerous applications and often preferred over other geometric triangulations . the question arises why the delaunay triangulation is better than others . in the plane , the advantages of delaunay triangulation are sometimes rationalized by the max - min angle criterion @xcite . it requires that the diagonal of every convex quadrangle should be chosen to maximize the minimum of the six angles in the two triangles making up the quadrangle @xcite . it follows that the delaunay triangulation lexicographically maximizes the non - decreasing sequence of angles . triangulations of the same finite collection of points in @xmath8 dimensions can have different length sequences of angles . instead of comparing them directly , we may consider a functional , which assigns a real number to every triangulation . in this paper , we consider functionals that are defined for @xmath1-simplices and we assign the sum of the values over all @xmath1-simplices to the triangulation . for example , instead of the angle sequence we may consider the functional that maps a triangulation to the sum of minimum angles of @xmath1-simplices . in @xmath7 , this functional attains its minimum for the delaunay triangulation . other functionals that attain their minimum for the delaunay triangulation in the plane have been studied in @xcite and generalized from finite collections to ( infinite ) delone sets in @xcite . for example , the rajan functional is defined by mapping a triangle @xmath9 with edges of length @xmath10 to @xmath11 times the area of @xmath9 . there is an intuitive geometric interpretation obtained by lifting a point with coordinates @xmath12 and @xmath13 to @xmath14 , which is a point on the standard paraboloid in @xmath15 . similarly , we lift @xmath9 to a triangle in space , namely the one spanned by the three lifted vertices . the rajan functional maps @xmath9 to the volume between the paraboloid and the lifted triangle , of course restricted to the vertical prism over @xmath9 . the rajan functional of a geometric triangulation is therefore the volume between the paraboloid and the lifted triangulation . since the delaunay triangulation corresponds to taking the convex hull of the lifted points @xcite , it is easy to see that the delaunay triangulation minimizes this functional . the focus in this paper is a related concept , which we refer to as the _ voronoi functional _ ; see also @xcite . for a triangle @xmath9 with acute angles , it is the volume below the standard paraboloid and above the tangent planes that touch the paraboloid in the lifted vertices of @xmath9 , again restricted to the vertical prism above @xmath9 . the definition can be extended to triangles with non - acute angles and to @xmath1-simplices , as we will explain in the body of this paper . our main results are a characterization of the voronoi functional for triangulations in @xmath7 in terms of squared euclidean distances to the given points , and a proof that the voronoi functional attains its maximum for the delaunay triangulation ; see the voronoi cell decomposition and the voronoi optimality theorems in section [ sec3 ] . while the voronoi functional is defined for topological triangulations of the given points , which allow for folding along edges , the optimality of the delaunay triangulation holds only within the smaller class of geometric triangulations . similarly , we have a counterexample to the optimality of the delaunay triangulation among the geometric triangulations of points in three and higher dimensions .    [ [ outline . ] ] outline . + + + + + + + +    section [ sec2 ] defines the voronoi functional for geometric and topological triangulations of points in @xmath7 . section [ sec3 ] introduces the circumcenter map , which is instrumental for the interpretation of the voronoi functional as a volume in @xmath15 , and it proves our two main results . section [ sec4 ] gives counterexamples to extending the optimality result . section [ sec5 ] concludes the paper . we introduce the voronoi functional in three steps , beginning with the relatively easy case of an acute triangle . [ [ acute - case . ] ] acute case . + + + + + + + + + + +    let @xmath16 be the vertices of an acute triangle , @xmath9 , in @xmath7 . for a point @xmath17 , we write @xmath18 for the vertex among the three that is nearest to @xmath17 , and we define @xmath19 to interpret @xmath20 geometrically , we introduce the unit paraboloid as the graph of @xmath21 defined by @xmath22 . setting @xmath23 , we note that the graph of @xmath24 is the tangent plane that touches the paraboloid in the point @xmath25 . the vertical distance between the paraboloid and the plane above a point @xmath26 is @xmath27 subdividing @xmath9 into regions of constant nearest vertex , we get three quadrangles . integrating the squared distance to the vertex over each quadrangle , and adding the results , we get @xmath20 as the volume between the paraboloid and the upper envelope of the three tangent planes ; see figure [ fig : voronoi - acute ] .    before extending @xmath20 to obtuse triangles , we develop an algebraic formula in the acute case . we use the notation of figure [ fig : voronoi - acute ] , assuming @xmath7 is spanned by the first two coordinate axes of @xmath15 , and @xmath28 is the common origin of @xmath7 and @xmath15 . without loss of generality , we may assume that @xmath29 is the circumcenter of @xmath9 . let @xmath30 be the area of the triangle , and @xmath31 the volume of the triangular prism bounded from below by @xmath9 and from above by the triangle with vertices @xmath32 . letting @xmath33 be the radius of the circumcircle , we have @xmath34 , and therefore @xmath35 . writing @xmath36 , @xmath37 , and @xmath38 for the quadrangles subdividing the acute triangle , we let @xmath39 be the volume of the quadrangular prism between @xmath40 and @xmath41 , and similar for @xmath42 and @xmath43 . unlike suggested by figure [ fig : voronoi - acute ] , the point @xmath44 is below @xmath29 , so that a portion of each quadrangular prism is below the horizontal coordinate plane . the notion of volume we use is signed , which means that @xmath39 is the ( unsigned ) volume of the portion above @xmath7 minus the ( unsigned ) volume of the portion below @xmath7 . writing @xmath45 , @xmath46 , and @xmath47 for the lengths of the three edges , we set @xmath48 this is known as the _ rajan functional _ , which is the volume between the paraboloid and the triangle @xmath49 . it is now easy to express the voronoi functional by subtracting the rajan functional and volumes of the three quadrangular prisms from the volume of the triangular prism : @xmath50 . after half a page of trigonometric calculations , we get @xmath51 see appendix b.    [ [ obtuse - case . ] ] obtuse case . + + + + + + + + + + + +    to extend the formula to the case of an obtuse triangle , it is convenient to further subdivide each quadrangle into two triangles by drawing the edges between @xmath29 and the three vertices . recalling that @xmath52 is the midpoint of the edge from @xmath53 to @xmath54 , we set @xmath55 and similarly for the other five triangles in the subdivision . in the acute case , we can rewrite to get @xmath56 let now @xmath9 be obtuse and use to define the voronoi functional of @xmath9 . assuming the angle at @xmath57 exceeds @xmath58 , we get @xmath59 see appendix a. this has a geometric interpretation , which we illustrate in figure [ fig : fold ] . in particular , two of the six triangles subdividing @xmath9 have negative orientation , namely @xmath60 and @xmath61 , and we record the volume of the corresponding triangular prisms with a minus sign . the reason for the negative orientation is that @xmath29 lies outside the triangle and , in the illustrated case , on the opposite side of the edge from @xmath53 to @xmath54 . besides the fold - over interpretation of @xmath20 , we will use the interpretation as the integral over a difference between two squared distances . call a vertex _ visible _ from @xmath17 if the line segment connecting @xmath17 to the vertex does not intersect @xmath9 other than in this vertex . writing @xmath62 for the nearest vertex of @xmath9 that is visible from @xmath17 , we have @xmath63 for points @xmath17 inside @xmath9 , @xmath62 is not defined and we set @xmath64 . this way we get a formula that is correct both for acute and for obtuse triangles . indeed , in the acute case , we have @xmath65 for all points @xmath17 outside @xmath9 , which implies that agrees with . in the obtuse case , we have @xmath66 for all points @xmath17 in the shaded region shown in figure [ fig : fold ] . in this case , @xmath20 is not the volume between the paraboloid and the three tangent planes restricted to the triangular prism , but rather something smaller than this volume .    [ [ in - the - large . ] ] in the large . + + + + + + + + + + + + +    we extend the voronoi functional by taking the sum over all triangles of a triangulation . specifically , letting @xmath67 be a triangulation of @xmath68 , we set @xmath69 what do we mean by a triangulation of @xmath70 ? most important is the _ delaunay triangulation _ that consists of all triangles spanned by three points of @xmath70 such that no point of @xmath70 is enclosed by the circumcircle of the triangle . assuming the points are in general position by which we mean that no four points lie on a common circle  the delaunay triangulation is well defined and unique .    a more general notion is a _ geometric triangulation _ , which is a simplicial complex in @xmath7 whose vertex set is @xmath70 and whose underlying space is @xmath71 . clearly , the delaunay triangulation is a geometric triangulation of @xmath70 , and in many ways , it is the most natural and most interesting geometric triangulation of the point set . more general yet is a _ topological triangulation _ , which is a simplicial complex homeomorphic to a disk whose vertex set is @xmath70 . in contrast to a geometric triangulation , the triangles of a topological triangulation may intersect as we think of them abstractly , worrying primarily about how they are connected . every geometric triangulation is also a topological triangulation but not the other way round . if no three points of @xmath70 are collinear , then every triangle of a topological triangulation maps to a geometric triangle , whose orientation may be positive or negative . we interpret accordingly , namely that the sign of @xmath20 is the same as that of the orientation of the triangle . we give a complete description of the voronoi functional for delaunay triangulations , and we prove that among the geometric triangulations of a finite set in @xmath7 , the delaunay triangulation maximizes the voronoi functional . [ [ the - circumcenter - map . ] ] the circumcenter map . + + + + + + + + + + + + + + + + + + + + +    let @xmath67 be a geometric triangulation of @xmath68 . the _ barycenter _ of a simplex @xmath72 is the point @xmath73 that is the average of the vertices of @xmath74 . a _ flag _ a sequence of simplices in @xmath67 such that each simplex is a proper face of its successor . the _ barycentric subdivision _ of @xmath67 is the simplicial complex , @xmath75 , whose vertices are the barycenters of the simplices in @xmath67 and whose simplices correspond to flags in @xmath67 ; see figure [ fig : sd ] . every @xmath72 has a unique smallest circle that passes through its vertices . we call the center of this circle the _ circumcenter _ , @xmath76 , and its radius the _ circumradius _ , @xmath77 , of the simplex . we introduce the _ circumcenter map _ and the _ height map _ , @xmath78 each the piecewise linear extension of a vertex map : the first such that @xmath79 , and the second such that @xmath80 , for every @xmath72 . as illustrated in figure [ fig : sd ] , the circumcenter map distorts the barycentric subdivision so it aligns with the voronoi diagram , with the exception of occasional fold - edges caused by obtuse triangles . the height map lifts the image of the circumcenter map to @xmath15 . to see how it does it , let @xmath81 be a vertex of @xmath67 , and consider its star in @xmath75 . a triangle , @xmath82 , in this star is spanned by the barycenters @xmath83 , @xmath84 , @xmath85 , with @xmath86 an edge , and @xmath87 a triangle in @xmath67 . the images under @xmath88 are the point , @xmath89 , the midpoint of the edge , @xmath90 , and the circumcenter of the triangle , @xmath91 . the corresponding heights are @xmath92 , @xmath93 , and @xmath94 . we see that the combined map , @xmath95 , sends the entire star of @xmath53 to the plane that is the graph of @xmath96 . similarly , the star of @xmath57 is sent to the graph of @xmath97 , and the star of @xmath54 is sent to the graph of @xmath98 . the stars are glued along shared boundary pieces , which must therefore lie in the common intersection of the planes . indeed , we have @xmath99 and @xmath100 . we use the two maps to recast the voronoi functional as an integral . write @xmath101 and @xmath102 for the signed areas of a triangle and its image under the circumcenter map . with this , we have @xmath103 the ratio in front of the integral captures the area distortion experienced by @xmath104 , and it is negative iff @xmath88 reverses the orientation of the triangle . geometrically , we interpret @xmath105 as the signed volume between the paraboloid and the lifted copy of @xmath106 . finally , @xmath107 is the sum of the @xmath105 , over all triangles @xmath108 .    [ [ inclusion - exclusion . ] ] inclusion - exclusion . + + + + + + + + + + + + + + + + + + + +    in the case in which @xmath109 is the delaunay triangulation of @xmath68 and all angles are acute , @xmath110 has a very appealing geometric interpretation as the volume of the body between the paraboloid and the upper envelope of the graphs of @xmath96 , @xmath81 , restricted to within the vertical prism over the convex hull of @xmath70 . this interpretation applies more generally , namely as long as the angles opposite to the convex hull edges are acute .    to explain why this is true , we consider an interior vertex @xmath53 ; see figure [ fig : stars ] on the left . let @xmath87 and @xmath111 be two triangles and @xmath112 the corresponding edge of the voronoi polygon . letting @xmath113 be the midpoint of the shared edge , @xmath114 , we have @xmath115 and @xmath116 as images under @xmath88 of two edges in @xmath75 . if the angles at @xmath57 and @xmath117 inside the mentioned triangles are acute , then @xmath113 lies in the interior of the voronoi edge , the triangles @xmath118 and @xmath119 both have the same orientation as their preimages under @xmath88 , and they decompose the triangle @xmath120 . to describe the other case , we consider the triangles @xmath111 and @xmath121 with corresponding edge @xmath122 of the voronoi polygon in figure [ fig : stars ] . if the angle at @xmath123 is obtuse , then the angle at @xmath54 is necessarily acute , and the midpoint @xmath124 of @xmath125 does not lie on the voronoi edge . instead , @xmath124 lies on the line of @xmath122 so that @xmath126 has the same orientation as its preimage under @xmath88 , and @xmath127 has the opposite orientation . subtracting the integral over @xmath127 from the integral over @xmath126 , we get again the integral over @xmath128 . adding the signed contributions of all triangles in the star , we get the integral over voronoi polygon . in contrast to , we formulate the claim by integrating over all points of the _ image _ of a triangle @xmath129 . we therefore replace the ratio of the determinants by its sign :    let @xmath53 be an interior vertex in the delaunay triangulation of a finite set @xmath68 . then @xmath130 where @xmath131 is the voronoi polygon of @xmath53 , and the sum is over all triangles @xmath104 in the star of @xmath53 inside the barycentric subdivision of the delaunay triangulation .    to generalize the lemma to boundary vertices , we may clip the necessarily infinite voronoi polygons to within the convex hull of @xmath70 . with this modification , the lemma holds provided the angles opposite to boundary edges are acute . indeed , the signed integrals over the triangles add up to the integral over the cone from @xmath53 to the finite edges of the voronoi polygon plus the finite pieces of the infinite edges that end at the midpoints of the boundary edges @xmath132 and @xmath86 ; see figure [ fig : stars ] on the right . to summarize , we let @xmath133 be the point in @xmath70 minimizing the distance to @xmath17 . let @xmath134 be the delaunay triangulation of a finite set @xmath68 . if all angles opposite to edges of the convex hull of @xmath70 are acute , then @xmath135    [ [ difference - of - squared - distances . ] ] difference of squared distances . + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +    to shed light on the general case , assume that @xmath87 is a triangle with boundary edge @xmath86 and obtuse angle at @xmath54 . the star of @xmath53 inside @xmath136 contains a linear sequence of triangles . removing the first triangle and the last , the signed areas add up to the area of the cone of @xmath53 over the finite edges of its voronoi polygon . since the angle at @xmath54 is obtuse , the cone extends outside the convex hull of @xmath70 , but that extension is covered by the negatively oriented first triangle in the linear sequence . this triangle covers more , so we have a remaining negative contribution , which is the integral over the region of points @xmath17 outside @xmath71 for which the nearest vertex in @xmath70 is not the nearest vertex on the boundary of @xmath71 ; see figure [ fig : stars ] on the right .    to write this more succinctly , we recall that @xmath18 and @xmath62 denote the nearest vertex and the nearest visible vertex of @xmath9 to @xmath26 . similarly , @xmath133 is the nearest point in @xmath70 to @xmath17 , and we write @xmath137 for the nearest visible vertex of @xmath71 to @xmath17 . for @xmath138 , @xmath137 is not defined and we set @xmath139 in this case . let @xmath134 be the delaunay triangulation of a finite set @xmath68 . then @xmath140    proof . write @xmath141 , and consider first the case in which all angles opposite to convex hull edges are acute . by , @xmath110 is the integral , over all points of @xmath71 , of @xmath142 . since @xmath137 of a point in the convex hull is not defined , this is the same as the integral of @xmath143 , still only over the convex hull of @xmath70 . for a point @xmath144 , we have @xmath145 by assumption on the angles . it follows that the contribution to the integral outside the convex hull vanishes , which implies the claimed equation in this special case .    to extend the equation to the general case , we note that next to each convex hull edge but outside the convex hull , we get a region of points where the contributions to the nearest visible vertices do not cancel ; see figure [ fig : stars ] on the right . any two such regions are disjoint , and the net effect within each region is the described difference between the squared distances to the nearest point of @xmath70 and the nearest visible vertex on the convex hull boundary . the claimed equation follows . [ [ optimality - of - the - delaunay - triangulation . ] ] optimality of the delaunay triangulation . + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +    we prove that the delaunay triangulation maximizes the voronoi functional . more than that , we show that the delaunay triangulation maximizes the functional locally , at every point of the plane . to explain this , define @xmath146 where the sum is over all triangles @xmath9 of a geometric triangulation @xmath67 of @xmath70 . with this notation , we get @xmath147 from . let @xmath134 be the delaunay triangulation and @xmath67 a geometric triangulation of a finite set @xmath68 . then @xmath148 . we prove optimality by showing @xmath149 for all @xmath26 . we have @xmath141 from the voronoi delaunay theorem , so it suffices to show @xmath150 . consider first a point @xmath138 . for the triangle that contains @xmath17 , we have @xmath151 , which is positive . for every other triangle , we have @xmath152 . let @xmath153 , and consider the sequence of triangles @xmath154 constructed as follows . if @xmath17 lies inside one of the triangles in the star of @xmath155 , then @xmath156 is this triangle , and @xmath157 . otherwise , there is a triangle @xmath158 such that the line segment from @xmath155 to @xmath17 crosses one of its edges . let @xmath159 be the nearest visible vertex of @xmath156 , and repeat the construction substituting @xmath159 for @xmath155 to get @xmath160 , and so on until @xmath161 contains @xmath17 or we formed a cycle . in the former case , the sum of squared distances is @xmath162 the right hand side evaluates to @xmath163 . the contribution of the triangles not in this sequence is non - positive , which implies @xmath164 . if in the latter case the cycle goes around the triangle that contains @xmath17 , then it must contain a vertex , @xmath165 , that is further from @xmath17 than the vertices of the containing triangle , and in particular further than the closest vertex of that triangle , @xmath166 . we stop the process at this vertex and get @xmath167 this time , the right hand side evaluates to @xmath168 . the triangle that contains @xmath17 is the only one with a positive contribution , which is @xmath169 , so that we again get @xmath170 , as desired .    we still need to show that if the vertices @xmath171 form a cycle , then it goes around the point @xmath17 . to derive a contradiction , we assume the cycle does not go around @xmath17 , as in figure [ fig : cycle ] . at each point @xmath166 of the cycle , we let @xmath172 be the counterclockwise rotation angle between the direction of the cycle at @xmath166 and the vector @xmath173 . this is a multivalued function , so we pick a branch by choosing its value at the starting point inside @xmath174 and requiring that @xmath175 be continuous along any edge , with right - continuous jumps at the vertices . the jump is positive at a counterclockwise turn and negative at a clockwise turn , never exceeding @xmath176 in absolute value . assuming the cycle is oriented in a counterclockwise order , @xmath175 grows by @xmath177 when we go around once . indeed , because @xmath17 lies outside the cycle , the continuous changes total to @xmath29 , and since the cycle is simple , the jumps total to @xmath177 . let @xmath171 be the vertex at which the jump changes @xmath175 from a value less than @xmath177 to a value at least @xmath177 . as illustrated in figure [ fig : cycle ] , the line passing through @xmath178 and @xmath171 separates @xmath17 from @xmath179 . but this implies that the edge connecting @xmath178 to @xmath171 crosses the edge of the triangle @xmath180 opposite to @xmath171 . this contradicts that both edges belong to @xmath67 and concludes the proof that the cycle must go around @xmath17 .    to extend the argument to points @xmath17 outside the convex hull of @xmath70 , we note that @xmath181 and @xmath182 are both non - positive . let @xmath33 be the region of points with @xmath183 and note that it is bounded . we can therefore add vertices and triangles on the outside , maintaining that we still have a delaunay triangulation , such that @xmath33 is completely covered by the added triangles . adding the same triangles to @xmath67 , we get two new triangulations , @xmath184 and @xmath185 , and we have @xmath186 for every @xmath187 using the above argument . since we add the same triangles to @xmath134 and to @xmath67 , we have @xmath188 , which implies @xmath149 also for the points @xmath187 . for the remaining points , @xmath189 , we have @xmath190 by definition of @xmath33 , and @xmath191 because @xmath17 lies outside the underlying space of @xmath67 . we thus get @xmath149 for all points @xmath26 , as claimed . in this section , we show that the optimality of the delaunay triangulation among all geometric triangulation of a finite point set does not generalize if we extend the family to all topological triangulations . furthermore , we show that even without this extension , the optimality of the delaunay triangulation does not extend to three dimensions . consider the triangulation in figure [ fig : folded ] on the left . all triangles are acute , which implies that this is the delaunay triangulation , @xmath134 , of the eight points . the topological triangulation , @xmath67 , of the same eight points is obtained by exchanging the positions of points @xmath192 and @xmath193 , moving the edges and triangles along to preserve all incidences ; see figure [ fig : folded ] on the right . the pentagons @xmath194 and @xmath195 are covered only once by @xmath67 , while @xmath196 is covered three times . we prove @xmath197 by computing @xmath198 for every point @xmath26 . all triangles in @xmath67 are acute , which implies that the only non - zero terms come from triangles that contain @xmath17 . first consider @xmath17 inside @xmath87 , and note that the case @xmath17 inside @xmath199 is symmetric . here @xmath17 is covered by @xmath87 , which has negative orientation , and by two triangles with positive orientation , namely one of @xmath200 and @xmath201 and one of @xmath202 and @xmath203 . in every case , @xmath181 is the sum of the squared distances to the nearest vertices of these triangles : @xmath204 , in which @xmath205 we have @xmath206 because @xmath17 is closer to @xmath54 than to @xmath123 and @xmath207 . similarly , @xmath208 . this implies @xmath209 with strict inequality on a set of positive measure . next consider @xmath17 inside the region @xmath194 , and note that the case of @xmath17 inside @xmath195 is symmetric . the region is covered only once , by triangles @xmath200 , @xmath210 , @xmath211 , all of which have positive orientation . since all three triangles are acute , @xmath181 is the squared distance of the closest vertex of the pentagon @xmath212 , while @xmath182 is the squared distance to the closest vertex of @xmath194 . point @xmath57 is further from all points within the pentagon than @xmath54 , which again implies @xmath213 . all triangles are acute , so @xmath214 outside @xmath215 . in summary , @xmath213 for all points @xmath26 , and the inequality is strict on a set of positive measure . hence , @xmath216 as claimed .      we may generalize the voronoi functional to three and higher dimensions , defining it as the sum , over all simplices in the barycentric subdivision , of the integral of the signed squared distance : @xmath217 where @xmath53 is the unique vertex of @xmath104 that is also a vertex of @xmath67 . in @xmath218 dimensions , the circumcenter map moves two vertices of a tetrahedron in the barycentric subdivision , possibly inverting a tetrahedron twice and thus returning it to positive orientation . this explains why there may be triangulations for which the voronoi functional exceeds that of the delaunay triangulation . [ [ double - fold - over . ] ] double fold - over . + + + + + + + + + + + + + + + + +    we exhibit a tetrahedron for which there are points not contained in the tetrahedron that have a positive contribution to the integral of the squared distance to the nearest vertex . in @xmath7 , a triangle with this property does not exist . figure [ fig : badtet ] shows the tetrahedron , @xmath219 , together with the center of the circumsphere , @xmath220 . the faces @xmath221 , @xmath222 are isosceles triangles with three acute angles each . in contrast , @xmath223 , @xmath224 are isosceles triangles with obtuse angles at @xmath57 and at @xmath117 , and we show the centers of their circumcircles : @xmath225 and @xmath226 . the circumcenter map leaves the four vertices and the midpoints of the edges fixed , and it moves the barycenters of the four triangles and of the tetrahedron to new locations . as a consequence , some of the images of the @xmath227 triangles in the barycentric subdivision of the boundary of @xmath219 change their orientation within their respective planes . because of the obtuse angles at @xmath57 and at @xmath117 , these are the four triangles that share the midpoint of @xmath114 . the other @xmath228 triangles preserve their orientation . the image of the barycenter of the tetrahedron is @xmath29 , the planes of @xmath223 and @xmath224 separate @xmath229 from @xmath29 , while the planes of @xmath221 and @xmath222 do not separate the two points . it follows that @xmath230 tetrahedra in the barycentric subdivision preserve their orientation , while @xmath231 tetrahedra reverse their orientation . just like in @xmath7 , where we have regions outside an obtuse triangle whose points contribute negatively to the voronoi functional ( see figure [ fig : fold ] ) , we have regions outside @xmath219 whose points contribute positively to the voronoi functional . specifically , there is such a point @xmath17 near @xmath123 inside the cone of @xmath29 over the blue triangle in figure [ fig : badtet ] . it satisfies @xmath232 , and its contribution to the voronoi functional is @xmath233 , which is positive . the argument used to prove the optimality of the delaunay triangulation in @xmath7 does therefore not apply .    [ [ counterexample . ] ] counterexample . + + + + + + + + + + + + + + +    inspired by the construction in figure [ fig : badtet ] , we use a numerical method for estimating the voronoi functional to find points in @xmath15 for which the delaunay triangulation does not maximize the functional . figure [ fig : counter ] illustrates one such example . there are six point with coordinates @xmath234 whose convex hull is an octahedron . the delaunay triangulation decomposes the octahedron into the four tetrahedra sharing the edge @xmath235 . we compare it with the triangulation , @xmath67 , whose four tetrahedra share the edge @xmath114 . the values of the voronoi functional are @xmath236 which shows that @xmath134 does not maximize the functional . as a by - product of the voronoi optimality theorem , we have the optimality of the delaunay triangulation for the functional that takes the sum over all triangles of the squared circumradius times the area . more generally , we define @xmath237 where @xmath238 is the circumradius of @xmath9 . indeed , @xmath239 so we conclude that @xmath240 attains its minimum at the delaunay triangulation . similarly , we can prove that @xmath241 attains its minimum at the delaunay triangulation . writing @xmath242 , we have @xmath243 and therefore @xmath244 . when we flip an edge to turn a geometric triangulation into the delaunay triangulation , the sum of @xmath245 can not increase , which implies the delaunay triangulation is optimal . it would be interesting to prove optimality for all @xmath246 . it might be interesting to generalize the voronoi functional to points with weights ; see e.g.  @xcite . the inclusion - exclusion argument presented in section [ sec3 ] extends to the weighted case , but is it true that the generalized voronoi functional is maximized by the delaunay triangulation for weighted points in @xmath7 ?    15    extremal properties of delaunay triangulations . _ trudy isa ras _ * 46 * ( 2009 ) , 174187 .    a spectral characterization of the delaunay triangulation . _ comput .  aided geom . design _ * 27 * ( 2010 ) , 295300 .    sur la sphre vide . nauk sssr , otdelenie matematicheskikh i estestvennykh nauk _ * 7 * ( 1934 ) , 793800 .    geometry of positive quadratic forms . _ uspekhi mat . nauk _ * 3 * ( 1937 ) 1662 . functionals on triangulations of delaunay sets . _ moscow math . j. _ * 14 * ( 2014 ) , 491504 . _ geometry and topology for mesh generation . _ cambridge univ .  press , cambridge , england , 2001 . three - dimensional triangulations from local transformations . _ siam j.  sci . statist . * 10 * ( 1989 ) , 718741 . the delaunay triangulation maximizes the mean inradius . _ in _ `` proc . 6th canad . geom . , 2994 '' , 201206 . software for @xmath247 surface interpolation . in _ mathematical software iii _ , ed . : j.  r.  rice , academic press , new york , 1977 , 161194 . properties of the delaunay triangulation . _ in _ `` proc . 13th ann . geom . , 1997 '' , 424426 .    about optimality of delaunay triangulations . in _ geometry , topology , algebra and number theory , applications _ , conf . dedicated to 120th anniversary of b.  n.  delone , ( 2010 ) , 166167 . problems in plane geometry  m. : mccme , 2006 . optimality of the delaunay triangulation in @xmath248 . _ discrete comput . * 12 * ( 1994 ) , 189202 . minimal roughness property of the delaunay triangulation . _ comput . aided geom .  design _ * 7 * ( 1990 ) , 489497 . locally equiangular triangulations . .  j. _ * 21 * ( 1978 ) , 243245 . nouvelles applications des parametres continus a la theorie des formes quadratiques . _ j.  reine angew . _ * 34 * ( 1908 ) , 198287 . as an alternative to the proof in section [ sec3 ] , we can show the optimality of delaunay triangulations for the voronoi functional via flips . more precisely , it is sufficient to show that the voronoi optimality theorem holds for any convex quadrangle . since the delaunay triangulation may be derived from any triangulation through a sequence of flips , this will imply that the theorem is true for all finite sets @xmath68 . let @xmath134 and @xmath67 be the delaunay and the non - delaunay triangulations of four points in convex position in @xmath7 . then @xmath249 for all @xmath26 . let @xmath250 be the four points in convex position , @xmath26 , and assume @xmath251 . then    1 . the edge @xmath252 belongs to the delaunay triangulation , because there is a circle ( centered at @xmath17 ) such that @xmath253 are on or inside , and @xmath254 are on or outside the circle , 2 . the points @xmath113 and @xmath124 do not lie inside the triangle @xmath255 , else they would be closer to @xmath17 than @xmath256 or @xmath257 . [ a ] implies that if @xmath252 is a diagonal of the quadrangle , then @xmath134 consists of the triangles @xmath258 . the remainder of the proof is a case analysis , which we illustrate in figure [ fig : cases ] . case i : :    @xmath17 is inside the quadrangle ; see figure [ fig : cases ] ,    @xmath259st row . +    case i.1 ; ;      @xmath252 is a side of the quadrangle . then      @xmath260      because the values for the two triangles are either      @xmath261      and @xmath29 , or      @xmath262      and      @xmath263 . ; ;      @xmath252 is a diagonal . using [ a ] , we get      @xmath264 ,      which is greater than or equal to      @xmath265 . case ii : :    @xmath17 lies outside , and only two vertices of the quadrangle    are visible from @xmath17 .    +    case ii.1 ; ;      @xmath252 is a side ; see figure [ fig : cases ] ,      @xmath266nd row . we have four subcases and      @xmath260      in each . +      case ii.1.a : :        both @xmath256 and @xmath257 are visible from        @xmath17 . then @xmath267 for all four        triangles . case ii.1.b : :        @xmath256 is visible and @xmath257 is invisible . then        @xmath267 for all four triangles . case ii.1.c : :        @xmath257 is visible and @xmath256 is invisible . in        both triangulations , the values for the two triangles are        @xmath29 and        @xmath268 . case ii.1.d : :        both @xmath256 and @xmath257 are invisible . for one        triangulation the values for the two triangles are        @xmath268        and        @xmath269 ,        while for the other triangulation the values are        @xmath270        and @xmath29 . case ii.2 ; ;      @xmath252 is a diagonal ; see figure [ fig : cases ] ,      @xmath218rd row . we have two subcases and      @xmath271      in each . by [ a ] we know which triangulation is delaunay . +      case ii.2.a : :        @xmath256 is visible and @xmath257 is invisible . then        @xmath272        and        @xmath273 . case ii.2.b : :        @xmath257 is visible and @xmath256 is invisible . then        @xmath274        and        @xmath275 . case iii : :    @xmath17 is outside the quadrangle and three vertices of the    quadrangle are visible from @xmath17 . +    case iii.1 ; ;      @xmath252 is a side ; see figure [ fig : cases ] ,      @xmath276th row . we have three subcases and      @xmath260      in each . +      case iii.1.a : :        @xmath256 is invisible . by [ b ] there is only one choice for        @xmath257 so that the line through @xmath17 and        @xmath256 separates @xmath257 from @xmath254 . both triangulations contain one triangle with value        @xmath29 and the other with        @xmath263 . case iii.1.b : :        @xmath257 is invisible . as in case iii.1.a , there is only        one choice for @xmath256 , and @xmath277        for all four triangles . case iii.1.c : :        @xmath256 and @xmath257 are both visible . then        @xmath278 for all four triangles . case iii.2 ; ;      @xmath252 is a diagonal ; see figure [ fig : cases ] ,      @xmath279th row . we have two subcases and      @xmath271      in each . by [ a ] we know which triangulation is delaunay . +      case iii.2.a : :        @xmath256 is invisible .        @xmath280        and        @xmath281 . case iii.2.b : :        @xmath257 is invisible . then        @xmath272        and        @xmath282 . case iii.2.c : :        that @xmath256 and @xmath257 are both visible is        impossible because it would contradict [ b ] . the case analysis is exhaustive , which implies @xmath283 , as claimed . we remark that a flip can have only two possible outcomes : it leaves the value of @xmath284 the same , or it increases this value by @xmath285 . the latter case happens iff the two vertices closest to @xmath17 form a diagonal . in this section , we derive formula , both for the acute and obtuse cases . we will be working in @xmath15 and denote the three cartesian coordinates by @xmath286 . the voronoi functional is invariant under planar isometries , so we may assume that the circumcenter of the triangle is at the origin . the points @xmath32 thus have a common @xmath287-coordinate , which is @xmath288 , and the @xmath287-coordinate of @xmath44 is @xmath289 . we denote the angles of @xmath87 by @xmath290 and the area of @xmath87 by @xmath291 . we begin with the formula from section [ sec2 ] : @xmath292 we divide the quadrangle @xmath40 into two triangles , @xmath293 and @xmath294 , and similarly for @xmath42 and @xmath43 . the triangles adjacent to side @xmath86 are congruent , and we denote both of them by @xmath295 . similarly , two of the other triangles are denoted by @xmath296 , and two by @xmath297 . now we rewrite : @xmath298 since @xmath299 is a prism , @xmath300 . to compute @xmath301 , @xmath302 , @xmath303 , we use the following result . let @xmath304 be a triangle with vertices @xmath305 , @xmath306 , and the plane @xmath304 perpendicular to the @xmath307-plane . then we have @xmath308 @xmath309 , in which @xmath310 .    proof . we draw the altitude @xmath311 to divide @xmath304 into @xmath312 and @xmath313 . then we can find the area under this triangle for each plane perpendicular to the @xmath17-axis and integrate it : @xmath314_0^{r\cos^2{\phi } }                 \\                  & = r^4 \tan{\phi } \left ( \tfrac{2}{3 } \cos^6{\phi }                                     - \tfrac{1}{2 } \cos^4{\phi } \right ) . \end{aligned}\ ] ] similarly , @xmath315 . writing @xmath316 , we get @xmath317 which evaluates to @xmath318 , as claimed . writing @xmath319 , we apply the lemma to all six triangles to obtain @xmath320 finally , we combine it with and : @xmath321 we use the identities @xmath322 where @xmath323 is the half - perimeter of @xmath87 , and @xmath324 is its inradius ( for details see ( * ? ? ? * , b ) ) . @xmath325 the sequence of calculations for the obtuse triangle is almost the same . assume that @xmath326 . then the formula is transformed to : @xmath327 in this case , @xmath328 . therefore , all further calculations are completely the same as in the acute case . ll @xmath68 & finite set of points + @xmath20 & voronoi functional of triangle + @xmath21 & unit paraboloid + @xmath24 & tangent plane + @xmath16 & vertices + @xmath329 & barycenters + @xmath330 & lifted points +   + @xmath72 & simplex in triangulation + @xmath108 & triangle in barycentric subdivision + @xmath331 & barycenter , circumcenter , circumradius + @xmath332 & circumcenter map + @xmath333 & height map +   + @xmath334 & nearest , nearest visible vertex + @xmath335 & nearest , nearest visible point + @xmath134 & delaunay triangulation + @xmath336 & sequence of triangles + @xmath337 & local voronoi functional * section [ sec1 ] : introduction . * section [ sec2 ] : the voronoi functional . * * @xmath20 . * * @xmath338 . * * @xmath107 . * section [ sec3 ] : geometric triangulations . * * _ circumcenter map_. * * _ height map_. * * interior cancellation lemma . * * voronoi cell decomposition theorem . * * voronoi optimality theorem . * section [ sec4 ] : non - optimality . * * section [ sec41 ] : topological triangulations . * * section [ sec42 ] : beyond two dimensions . * section [ sec5 ] : discussion . * * @xmath339 . * section [ appa ] : voronoi optimality by flipping . * * voronoi optimality theorem for flips . * section [ appb ] : calculations . * * angle lemma .
we introduce the voronoi functional of a triangulation of a finite set of points in the euclidean plane and prove that among all geometric triangulations of the point set , the delaunay triangulation maximizes the functional . this result 
 neither extends to topological triangulations in the plane nor to geometric triangulations in three and higher dimensions .