2025/04/06 by Sándor P. Fekete, Fekete, Sándor P., Phillip Keldenich +5
Computer Science · #Advanced Graph Theory Research #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #Topological and Geometric Data Analysis
paper · doi:10.48550/arxiv.2504.04412
openalex publication_date 2025/04/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.