Order-2 Delaunay Triangulations Optimize Angles
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866929610890936320 |
|---|---|
| author | Edelsbrunner, Herbert Garber, Alexey Saghafian, Morteza |
| author_facet | Edelsbrunner, Herbert Garber, Alexey Saghafian, Morteza |
| contents | 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 $π$. 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_18238 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Order-2 Delaunay Triangulations Optimize Angles Edelsbrunner, Herbert Garber, Alexey Saghafian, Morteza Combinatorics Computational Geometry Metric Geometry 05B45, 52C20, 68R05 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 $π$. 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. |
| title | Order-2 Delaunay Triangulations Optimize Angles |
| topic | Combinatorics Computational Geometry Metric Geometry 05B45, 52C20, 68R05 |
| url | https://arxiv.org/abs/2310.18238 |