News Detail

First Announcement: CG Challenge 2025

We are happy to announce the Seventh Computational Geometry Challenge, as part of CG Week in Kanazawa, Japan, June 23-27, 2025.

As in previous years, the objective will be to compute good solutions to instances of a difficult geometric optimization problem. The specific problem chosen for the 2025 Challenge is Minimum Non-Obtuse Triangulations, as follows.

Description

In the Planar Straight Line Graphs (PSLGs) variant of the Minimum Non-Obtuse Triangulation problem, the objective is to triangulate the convex hull of a given PSLG (G), which is defined by a set of vertices and edges laid out in a plane such that the edges do not cross except at their endpoints. The triangulation must incorporate the existing edges of (G) and can include the addition of Steiner points anywhere in the plane, including on these edges. The placement of Steiner points is particularly challenging because it can affect the geometric properties of adjacent faces, thus complicating the triangulation process. All triangles formed in the solution must be non-obtuse, with each angle not exceeding 90 degrees, and the solution seeks to minimize the total number of Steiner points. This problem is complex due to its geometric constraints and the interdependencies introduced by Steiner points, making it a computationally demanding task likely belonging to the NP-hard class of problems.

For a polygon, an example of a Minimum Non-Obtuse Triangulation can be found as Figure 1 in [3], see below.

Objective

Find a feasible non-obtuse triangulation using a minimum number of Steiner points.

Motivation

Historically, triangulations have been crucial for applications ranging from computer graphics and mesh generation to geographic information systems (GIS) and finite element analysis. In computer graphics, triangulating surfaces enables the rendering of three-dimensional objects with high precision and efficiency. In mesh generation, triangulations help in discretizing a continuous geometric space into simpler elements that can be easily processed for simulations and analyses, particularly in engineering and physics.

The importance of non-obtuse triangulations in computational geometry is particularly evident in solving partial differential equations using the finite element method. In this method, the domain is divided into triangles, with non-obtuse triangulations ensuring that the resulting matrices are Stieltjes—symmetric positive definite with non-positive off-diagonal entries. This specific matrix structure enhances the performance of iterative methods, such as block Gauss-Seidel, improving their convergence rates. The geometric constraint of avoiding obtuse angles in triangulations not only stabilizes numerical calculations but also optimizes the efficiency of computational processes, making non-obtuse triangulations a crucial consideration in scientific computing and numerical analysis.

Minimum Non-Obtuse Triangulations have been studied for quite a while, with references in DCG and SoCG going back to the 1980s [1], and connections to finite element analysis. Subsequent work considered bounds on the necessary numbers of Steiner points [2,3]. More recent work [4] considers an algorithm for Planar Straight Line Graphs (PSLGs) [2]. The computational complexity for simple polygons and polygons with holes remains an open question in the field.

Instances

A diverse collection of approximately 150 to 400 Planar Straight Line Graphs will be provided for the competition.

Credit

The underlying problem was suggested by Mikkel Abrahamsen, Copenhagen.

Challenge Team

Sándor Fekete, Phillip Keldenich, Dominik Krupke, Stefan Schirra

Advisory Board

Bill Cook, Andreas Fabri, Dan Halperin, Michael Kerber, Philipp Kindermann, Joe Mitchell, Kevin Verbeek

Timeline

A first batch of test instances will be released at the end of July 2024; the actual benchmark instances for the Challenge will be released in late September. The contest will close in early 2025.

References:

[1] Brenda S. Baker, Eric Grosse, Conor S. Rafferty: Nonobtuse Triangulation of Polygons. Discret. Comput. Geom. 3: 147-168 (1988) https://link.springer.com/article/10.1007/BF02187904

[2] Marshall W. Bern, David Eppstein: Polynomial-Size Nonobtuse Triangulation of Polygons. SoCG 1991: 342-350 https://doi.org/10.1145/109648.109686

[3] Marshall W. Bern, Scott A. Mitchell, Jim Ruppert: Linear-Size Nonobtuse Triangulation of Polygons. Discret. Comput. Geom. 14(4): 411-428 (1995). https://link.springer.com/article/10.1007/BF02570715

SoCG version: Marshall W. Bern, Scott A. Mitchell, Jim Ruppert: Linear-Size Nonobtuse Triangulation of Polygons. SCG 1994: 221-230 https://dl.acm.org/doi/abs/10.1145/177424.177974

[4] Christopher J. Bishop: Nonobtuse Triangulations of PSLGs. Discret. Comput. Geom. 56(1): 43-92 (2016) https://link.springer.com/article/10.1007/s00454-016-9772-8