{Engineering Greedy Heuristics and Simulated Annealing Methods for the Median Triangulation Under the Parallel Flip Distance}
We present our approach for the CG:SHOP 2026 challenge. In this international challenge, the goal was to find a median triangulation for a set of triangulations in the parallel flip reconfiguration graph of all triangulations of an underlying point set. Our simulated-annealing-based approach makes use of two ingredients: a heuristic edge selection for approximating the parallel flip distance of two given triangulations, and a heuristic procedure to generate good initial triangulations.
- Published in:
42nd International Symposium on Computational Geometry (SoCG 2026) - Type:
Inproceedings - Authors:
- Year:
2026 - Source:
https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.106
Citation information
: {Engineering Greedy Heuristics and Simulated Annealing Methods for the Median Triangulation Under the Parallel Flip Distance}, 42nd International Symposium on Computational Geometry (SoCG 2026), 2026, 367, May, Schloss Dagstuhl -- Leibniz-Zentrum für Informatik, https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.106, Conradi.etal.2026a,
@Inproceedings{Conradi.etal.2026a,
author={Conradi, Jacobus; Kolbe, Benedikt; Mayer, Philip; Sauer, Jonas; Spalding-Jamieson, Jack},
title={{Engineering Greedy Heuristics and Simulated Annealing Methods for the Median Triangulation Under the Parallel Flip Distance}},
booktitle={42nd International Symposium on Computational Geometry (SoCG 2026)},
volume={367},
month={May},
publisher={Schloss Dagstuhl -- Leibniz-Zentrum für Informatik},
url={https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.106},
year={2026},
abstract={We present our approach for the CG:SHOP 2026 challenge. In this international challenge, the goal was to find a median triangulation for a set of triangulations in the parallel flip reconfiguration graph of all triangulations of an underlying point set. Our simulated-annealing-based approach makes use of two ingredients: a heuristic edge selection for approximating the parallel flip distance of...}}