2026-07-22T00:02:23Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25911 2026-06-23T13:00:40Z ddc:004 open_access

ETH Flippers Approach to Parallel Reconfiguration of Triangulations: SAT Formulation and Heuristics (CG Challenge) Battini, Lorenzo Milenković, Marko exact solution heuristic SAT solver XOR clauses computational geometry 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Lorenzo Battini and Marko Milenković 2026 Is Part Of LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2026.105 urn:nbn:de:0030-drops-259115 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.105 eng https://creativecommons.org/licenses/by/4.0/legalcode