ETH Flippers Approach to Parallel Reconfiguration of Triangulations: SAT formulation and Heuristics
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866908907332435968 |
|---|---|
| author | Battini, Lorenzo Milenković, Marko |
| author_facet | Battini, Lorenzo Milenković, Marko |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_22456 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | ETH Flippers Approach to Parallel Reconfiguration of Triangulations: SAT formulation and Heuristics Battini, Lorenzo Milenković, Marko 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. |
| title | ETH Flippers Approach to Parallel Reconfiguration of Triangulations: SAT formulation and Heuristics |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2603.22456 |