Order-2 Delaunay Triangulations Optimize Angles
| Autor: | Edelsbrunner, Herbert, Garber, Alexey, Saghafian, Morteza |
|---|---|
| Rok vydání: | 2023 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | 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 $\pi$. 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. Comment: 30 pages, 8 figures |
| Databáze: | arXiv |
| Externí odkaz: |
|