Computing Non-Obtuse Triangulations with Few Steiner Points
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866918038078488576 |
|---|---|
| author | Abrahamsen, Mikkel Brunck, Florestan Conradi, Jacobus Kolbe, Benedikt Nusser, André |
| author_facet | Abrahamsen, Mikkel Brunck, Florestan Conradi, Jacobus Kolbe, Benedikt Nusser, André |
| contents | We present the winning implementation of the Seventh Computational Geometry Challenge (CG:SHOP 2025). The task in this challenge was to find non-obtuse triangulations for given planar regions, respecting a given set of constraints consisting of extra vertices and edges that must be part of the triangulation. The goal was to minimize the number of introduced Steiner points. Our approach is to maintain a constrained Delaunay triangulation, for which we repeatedly remove, relocate, or add Steiner points. We use local search to choose the action that improves the triangulation the most, until the resulting triangulation is non-obtuse. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_23375 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Computing Non-Obtuse Triangulations with Few Steiner Points Abrahamsen, Mikkel Brunck, Florestan Conradi, Jacobus Kolbe, Benedikt Nusser, André Computational Geometry We present the winning implementation of the Seventh Computational Geometry Challenge (CG:SHOP 2025). The task in this challenge was to find non-obtuse triangulations for given planar regions, respecting a given set of constraints consisting of extra vertices and edges that must be part of the triangulation. The goal was to minimize the number of introduced Steiner points. Our approach is to maintain a constrained Delaunay triangulation, for which we repeatedly remove, relocate, or add Steiner points. We use local search to choose the action that improves the triangulation the most, until the resulting triangulation is non-obtuse. |
| title | Computing Non-Obtuse Triangulations with Few Steiner Points |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2505.23375 |