DROPS

Artifact

Software

ETH flippers CGSHOP2026

Authors: Lorenzo Battini and Marko Milenković

Abstract

Cite as

Lorenzo Battini, Marko Milenković. ETH flippers CGSHOP2026 (Software). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@misc{dagstuhl-artifact-26084,
   title = {{ETH flippers CGSHOP2026}}, 
   author = {Battini, Lorenzo and Milenkovi\'{c}, Marko},
   note = {Software, swhId: \href{https://archive.softwareheritage.org/swh:1:dir:ec12f1b858c98832fd57fc7a2d407989c1fc00cf}{\texttt{swh:1:dir:ec12f1b858c98832fd57fc7a2d407989c1fc00cf}} (visited on 2026-05-27)},
   url = {https://github.com/Lbattini/ETH-flippers-CGSHOP2026},
   doi = {10.4230/artifacts.26084},
}

Document

CG Challenge

DOI: 10.4230/LIPIcs.SoCG.2026.105

ETH Flippers Approach to Parallel Reconfiguration of Triangulations: SAT Formulation and Heuristics (CG Challenge)

Authors: Lorenzo Battini and Marko Milenković

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

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.

Cite as

Lorenzo Battini and Marko Milenković. ETH Flippers Approach to Parallel Reconfiguration of Triangulations: SAT Formulation and Heuristics (CG Challenge). In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 105:1-105:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{battini_et_al:LIPIcs.SoCG.2026.105,
  author =	{Battini, Lorenzo and Milenkovi\'{c}, Marko},
  title =	{{ETH Flippers Approach to Parallel Reconfiguration of Triangulations: SAT Formulation and Heuristics}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{105:1--105:6},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.105},
  URN =		{urn:nbn:de:0030-drops-259115},
  doi =		{10.4230/LIPIcs.SoCG.2026.105},
  annote =	{Keywords: exact solution, heuristic, SAT solver, XOR clauses, computational geometry}
}

Search Results

Documents authored by Milenković, Marko

ETH flippers CGSHOP2026

Abstract

Cite as

ETH Flippers Approach to Parallel Reconfiguration of Triangulations: SAT Formulation and Heuristics (CG Challenge)

Abstract

Cite as

Thanks for your feedback!

Could not send message