ETH Flippers Approach to Parallel Reconfiguration of Triangulations: SAT formulation and Heuristics
This work addresses a specific computational geometry challenge for the CG:SHOP 2026 competition, representing an incremental improvement with tailored methods.
The paper tackled the problem of finding a central triangulation that minimizes total parallel flip distance to a set of input triangulations, combining exact SAT solvers for small instances with heuristics for larger ones, achieving second overall and first in the junior category with provably optimal solutions for 186 out of 250 instances.
We describe the algorithms used by the ETH Flippers team in the CG:SHOP 2026 Challenge. Each instance consists of a set of triangulations on a common point set, and the objective is to find a central triangulation that minimizes the total parallel flip distance to the input set. Our strategy combines an exact solver for small and medium-sized instances with a suite of heuristics for larger instances. For the exact approach, we formulate the problem as a SAT instance with XOR clauses to model edge transitions across multiple rounds, further optimized by lower bounds derived from exact pairwise distances. For larger instances, we use a greedy local search and edge-coloring techniques to identify maximal sets of independent flips. Our approach ranked second overall and first in the junior category, computing provably optimal solutions for 186 out of 250 instances.