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/
*
**********************************************************
Posts
