A local-search solver over constrained Delaunay triangulations with insertion, relocation, deletion, and solution merging won CG:SHOP 2025, beating the runner-up on most instances.
Minimum Non-Obtuse Triangulations: The CG:SHOP Challenge 2025
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
We give an overview of the 2025 Computational Geometry Challenge targeting the problem Minimum Non-Obtuse Triangulation: Given a planar straight-line graph G in the plane, defined by a set of points in the plane (representing vertices) and a set of non-crossing line segments connecting them (representing edges); the objective is to find a feasible non-obtuse triangulation that uses a minimum number of Steiner points. If no triangulation without obtuse triangles is found, the secondary objective is to minimize the number of obtuse triangles in the triangulation.
fields
cs.CG 1years
2025 1verdicts
ACCEPT 1representative citing papers
citing papers explorer
-
Computing Non-Obtuse Triangulations with Few Steiner Points
A local-search solver over constrained Delaunay triangulations with insertion, relocation, deletion, and solution merging won CG:SHOP 2025, beating the runner-up on most instances.