We are happy to provide further details for the CG Challenge 2025:
https://cgshop.ibr.cs.tu-bs.de/competition/cg-shop-2025/#problem-description
At this site, you can also find a first set of test instances, along
with some visualizations.
We also did some adjustments to make the Challenge more accessible
and motivating for student teams. We understand that some instances
may not yield feasible solutions or that obtaining such solutions numerically
can be extremely challenging. To ease the learning curve for students, we
will divide the scoring into two phases and also award credit for near-feasible
solutions. While feasible solutions will always receive higher scores, this
approach will help reduce barriers and encourage students to get started.
If you have any comments or questions, please do not hesitate to
contact us!
Best wishes and happy optimizing,
Sándor Fekete
> Am 28.06.2024 um 20:04 schrieb Fekete, Sándor <s.fekete@tu-braunschweig.de>:
>
> Dear colleagues,
>
> 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.
> • First test instances: July 31, 2024
> • Contest instances: September 30, 2024
> • Contest Closes: January 22, 2024 (AOE)
>
> 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
>
>
>
**********************************************************
*
* Contributions to be spread via DMANET are submitted to
*
* DMANET@zpr.uni-koeln.de
*
* Replies to a message carried on DMANET should NOT be
* addressed to DMANET but to the original sender. The
* original sender, however, is invited to prepare an
* update of the replies received and to communicate it
* via DMANET.
*
* DISCRETE MATHEMATICS AND ALGORITHMS NETWORK (DMANET)
* http://www.zaik.uni-koeln.de/AFS/publications/dmanet/
*
**********************************************************
Posts
