Order-2 Delaunay Triangulations Optimize Angles

Abstract

The local angle property of the (order-$1$) Delaunay triangulations of a generic set in ${\mathbb{R}}^2$ asserts that the sum of two angles opposite a common edge is less than $\ddot{I}€$. This paper extends this property to higher order and uses it to generalize two classic properties from order-$1$ to order-$2$: (1) among the complete level-$2$ hypertriangulations of a generic point set in ${\mathbb{R}}^2$, the order-$2$ Delaunay triangulation lexicographically maximizes the sorted angle vector; (2) among the maximal level-$2$ hypertriangulations of a generic point set in ${\mathbb{R}}^2$, the order-$2$ Delaunay triangulation is the only one that has the local angle property. We also use our method of establishing (2) to give a new short proof of the angle vector optimality for the (order-1) Delaunay triangulation. For order-$1$, both properties have been instrumental in numerous applications of Delaunay triangulations, and we expect that their generalization will make order-$2$ Delaunay triangulations more attractive to applications as well.

32 pages, 9 figures