A first set of examples instances are now posted:
https://cgshop.ibr.cs.tu-bs.de/competition/cg-shop-2026/#problem-description
Use the „Download" button in the upper right.
At this point, these are only for preparation and training purposes.
Actual Challenge instances can expected to be more numerous,
larger in size, and also more challenging.
Feedback, comments or questions are welcome!
Best wishes,
Sándor Fekete
> Am 29.08.2025 um 16:01 schrieb Fekete, Sandor <s.fekete@tu-braunschweig.de>:
>
> Dear colleagues,
>
> We are happy to announce the Eighth Computational Geometry Challenge,
> as part of CG Week in New Brunswick, USA, June 2-5, 2026.
>
> 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 2026 Challenge is Central Triangulation under Parallel Flip
> Operations, as follows.
>
> Description
>
> Given a set of $m$ triangulations $T_1,\ldots,T_m$ on the same set $P$ of
> $n$ points in the plane, this year's challenge problem asks for a central
> triangulation $C$ on $P$ such that the number of parallel flip operations
> to reach the $T_i$ from $C$ is minimized.
>
> More formally, given $T_1,\ldots,T_m$, the goal is to compute $C$ and
> $m$ sequences of parallel flip operations $F_i$, each transforming $C$
> into $T_i$. The objective value $\obj(F_1,\ldots,F_m)$ of such a solution
> is $\sum_{i=1}^m |F_i|$, where $|F_i|$ denotes the number of parallel
> flips in $F_i$.
>
> In a triangulation $T$, a parallel flip is a set $D$ of diagonals of convex
> quadrilaterals (flippable edges) such that no two $e,e' \in D$ share a
> triangle. Performing a parallel flip operation transforms $T$ into another
> triangulation $T'$ by replacing each $e \in D$ by the other diagonal of
> the convex quadrilateral containing $e$.
>
> The following example shows an instance with three given triangulations
> for which a central triangulation of cost 7 can be found.
>
> Motivation
> Reconfiguration is the process of changing a structure into another -
> either through continuous motion or through discrete changes. In
> Discrete and Computational Geometry, reconfiguration has received
> particular attention in the context of triangulations, where a parallel flip
> exchanges one or more (independent) edge(s) of the triangulation
> for one or more other edge(s), such that the resulting graph is again
> a triangulation."
>
> Instances
> A diverse collection of instances will be provided for the competition.
> See the website https://cgshop.ibr.cs.tu-bs.de/ for details of upcoming
> (and previous) competitions and instances.
>
> Credit
> The underlying problem was suggested by
> Oswin Aichholzer, Joseph Dorfer, and Peter Kramer.
>
> Challenge Team
> Oswin Aichholzer, Joseph Dorfer, Sándor Fekete, Phillip Keldenich,
> Peter Kramer, 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 by the middle of
> September; the actual benchmark instances for the Challenge
> will be released in the middle of October. The contest will close
> in late January 2026.
>
> • First test instances: September 15, 2025
> • Contest instances: October 15, 2025
> • Contest Closes: January 29, 2026 (AOE)
>
> References:
> [1] Prosenjit Bose and Ferran Hurtado:
> Flips in planar graphs.
> Computational Geometry, Volume 42, 2009, pages 60-80.
> https://doi.org/10.1016/j.comgeo.2008.04.001
>
> [2] Iyad Kanj, Ge Xia:
> Flip Distance Is in FPT Time O(n+ k * c^k)
> STACS 2015, pages 500–512.
> https://doi.org/10.4230/LIPIcs.STACS.2015.500
>
> [3] Marshall W. Bern, Scott A. Mitchell, Jim Ruppert:
> An O (3.82^ k) Time Algorithm for Convex Flip Distance.
> Discret. Comput. Geom. 14(4): 411-428 (1995).
> https://doi.org/10.1007/s00454-023-00596-9
>
> [4] David Eppstein:
> Happy endings for flip graphs.
> SoCG 2007, pages 92-101.
> https://dl.acm.org/doi/abs/10.1145/1247069.1247084
>
> [5] Philip Mayer and Petra Mutzel:
> Engineering A* Search for the Flip Distance of Plane Triangulations.
> SEA 2024, pages 23:1-23:20.
> https://doi.org/10.4230/LIPIcs.SoCG.2022.7
>
**********************************************************
*
* 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/
*
**********************************************************