ETH Flippers Approach to Parallel Reconfiguration of Triangulations: SAT formulation and Heuristics
Lorenzo Battini, Marko Milenković · 2026
Read ETH Flippers Approach to Parallel Reconfiguration of Triangulations: SAT formulation and Heuristics by Lorenzo Battini, Marko Milenković (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-22456.txt.
Introduction
Battini and Milenković describe the ETH Flippers entry to a geometry challenge on triangulations. Each instance gives several triangulations of one point set, and the goal is a central one close to all inputs. Their distance counts parallel edge flips. For small and medium cases they encode the search as a SAT problem with extra bounds. For large cases they switch to greedy local search and edge coloring. The entry placed second overall and proved optimal answers for most instances.
Catalog record
| CREATOR | Lorenzo Battini, Marko Milenković |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 37603 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.22456
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
ETH Flippers Approach to Parallel Reconfiguration of Triangulations: SAT formulation and Heuristics Lorenzo Battini, Marko Milenković Abstract 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. ETH Zürich, [email protected]://orcid.org/0009-0009-7055-2277ETH Zürich, Switzerland and https://sites.google.com/view/sprdalo [email protected]://orcid.org/0009-0004-7925-7219 We would like to thank the Challenge organizers and other competitors for their time, feedback, and for making this whole event possible. This work was conducted as part of the Practical Work course at ETH Zürich under the supervision of Michael Hoffmann, whose guidance was invaluable. We sincerely thank Bernd Gärtner for providing travel support to attend the conference. We also acknowledge the ETH High Performance Computing group for providing the computational resources of the Euler cluster. ccs Theory of Computation \rightarrow Computational Geometry keywords exact solution, heuristic, SAT solver, XOR clauses, computational geometry † † runningtitle: ETH Flippers Approach to Parallel Reconfiguration of Triangulations † † runningauthor: L. Battini and M. Milenković † † copyright: Lorenzo Battini and Marko Milenković † † category: CG Challenge † † supplement: https://github.com/Lbattini/ETH-flippers-CGSHOP2026 1 Introduction Triangulations of point sets, in this context, maximal straight-line crossing-free graphs with endpoints in the point set, have many applications, for instance, in computer graphics and in reconstruction problems in geodesy. A common problem is transforming a triangulation into another on the same point set using edge flips, replacing an internal edge whose incident triangles form a convex quadrilateral with its other diagonal. Hurtado, Noy, and Urrutia [ 9 ] introduced parallel edge flips, which consist of flipping at the same time a set of edges such that none of the pairs of edges in the set shares a triangle. The “CG:SHOP Challenge” (Computational Geometry: Solving Hard Optimization Problems) is a computational challenge competition about a hard geometric optimization problem. This year’s challenge problem was proposed by Aichholzer, Dorfer, and Kramer. The goal is to find a central triangulation C and, for each of the given m triangulations T_{1},T_{2},\ldots,T_{m} on the same pointset P , a sequence of parallel flips transforming T_{i} into C , such that the sum of the lengths of these sequences is minimized. The solution methods are evaluated on a benchmark of 250 instances. We refer to [ 1 ] for further challenge details. We present an exact solution method based on formulating the problem as a SAT problem with XOR clauses, which is used to solve the small and medium instances, as well as various heuristics that we used for the larger instances. Our team, ETH flippers, ranked second overall and first in the junior category. We computed a provably optimal solution for 186 instances. Three further instances were solved, but a technical bug during our local validation caused us to stop at sub-optimal values. The largest instances we optimally solved featured twenty 320 -point triangulations, while the highest total parallel flip distance among our optimally solved instances is 92 . Notably, for this latter instance ( random_instance_440_160_20 ), our solution was uniquely the best among all participating teams (see Figure 1 ). Figure 1: Our best centers to instances random_instance_440_160_20 , woc -70- random -9 a7d18d3 , rirs -500-50-23 d00ec5 . 2 2-SAT formulation Given a set of m triangulations, \mathcal{T}=\{T_{1},T_{2},\dots,T_{m}\} , we formulate a 2-SAT instance to search for a triangulation C such that the distance from each T_{i}\in\mathcal{T} to C is at most one. For every convex quadrilateral q formed by a pair of facial triangles that share an edge in any T_{i} , we fix an arbitrary reference diagonal. Let the variable x_{q} denote whether C uses its reference diagonal and let the constant b_{q}^{(i)} denote its state in T_{i} . To prevent invalid simultaneous flips, we add the clause \neg(b_{q}^{(i)}\oplus x_{q})\lor\neg(b_{q^{\prime}}^{(i)}\oplus x_{q^{\prime}}) for all pairs of intersecting quadrilaterals q,q^{\prime} in each T_{i} . This determines the existence of a central triangulation C in \mathcal{O}(mn) time. 3 SAT formulation with XOR clauses XOR clauses. The most natural approach to modelling parallel flips is a round-by-round progression. We need to keep the state of each edge across intermediate parallel flips. We model the state transition of an edge e over k parallel flips using XOR operations. Let e^{0},e^{k}\in\{0,1\} denote the presence of e in the initial and final triangulations, respectively. Let \{q_{1},\dots,q_{g}\} be the set of all potential convex empty quadrilaterals that share e as a diagonal. We let f_{i}^{j}\in\{0,1\} indicate whether a flip is performed on q_{i} during step j . Because the final state of edge e after k parallel flips is simply its initial state XORed with all intermediate flips across its potential quadrilaterals q_{1\dots g} , we add the constraint e^{0}\oplus e^{k}\oplus\bigoplus_{j=1}^{k}\bigoplus_{i=1}^{g}f_{i}^{j}=0 We decided to use the CryptoMiniSat5 [ 15 ] solver, since it supports inputs with XOR clauses. 3.1 Formulation We extend the previous formulation to search for a center C whose distance to each T_{i}\in\mathcal{T} is upper bounded by a given target d[i] . Geometric Preconditions for Flips. Let \mathcal{Q} be the set of all convex empty quadrilaterals defined on the pointset, which we identified via spatial hashing [ Teschner2003 ] . Let the variable e_{uv}^{t} denote the presence of edge (u,v) at step t . For a flip f_{q}^{t}\in\{0,1\} to be geometrically valid at step t , the four boundary edges \partial q of its corresponding quadrilateral q\in\mathcal{Q} must exist in the prior step. We enforce this constraint with implication f_{q}^{t}\implies\bigwedge_{(u,v)\in\partial q}e_{uv}^{t-1} . Target Equivalence with Center C. We introduce global boolean variables c_{uv} representing the edges of the center C . We enforce consistency at the final step k via the equivalence e_{uv}^{k}\iff c_{uv} . This link forces the final state of every flip sequence to be identical to the global center, effectively merging the independent SAT sub-problems to a shared solution. Edge Transition Constraints. We must ensure that the triangulation changes only through valid flip operations. An edge (u,v) changes its status (present or absent) between parallel flips t-1 and t if and only if a flip is performed on a quadrilateral where (u,v) serves as the diagonal. Let \mathcal{Q}_{uv} be the set of all convex empty quadrilaterals for which (u,v) is a diagonal. The relationship between the edge’s state at consecutive parallel flips and the flip variables is enforced via an XOR constraint: e_{uv}^{t-1}\oplus e_{uv}^{t}\oplus\bigoplus_{q\in\mathcal{Q}_{uv}}f_{q}^{t}=0 . For edges on the convex hull, the set \mathcal{Q}_{uv} is empty, effectively enforcing that these edges remain constant throughout the transformation. Constraints on Simultaneous Flips. We must enforce strict independence between simultaneous operations. Specifically, for any subset of four vertices