Engineering Greedy Heuristics and Simulated Annealing Methods for the Median Triangulation Under the Parallel Flip Distance (CG Challenge)
Conradi, Jacobus; Kolbe, Benedikt; Mayer, Philip ; Sauer, Jonas
1; Spalding-Jamieson, Jack; Ahn, Hee-Kap [Hrsg.]; Hoffmann, Michael [Hrsg.]; Nayyeri, Amir [Hrsg.]
1 Institut für Theoretische Informatik (ITI), Karlsruher Institut für Technologie (KIT)
1; Spalding-Jamieson, Jack; Ahn, Hee-Kap [Hrsg.]; Hoffmann, Michael [Hrsg.]; Nayyeri, Amir [Hrsg.]1 Institut für Theoretische Informatik (ITI), Karlsruher Institut für Technologie (KIT)
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 two given triangulations, and a heuristic procedure to generate good initial triangulations.
| Zugehörige Institution(en) am KIT | Institut für Theoretische Informatik (ITI) |
| Publikationstyp | Proceedingsbeitrag |
| Publikationsjahr | 2026 |
| Sprache | Englisch |
| Identifikator | ISBN: 978-3-95977-418-5 ISSN: 1868-8969 KITopen-ID: 1000194441 |
| Erschienen in | 42nd International Symposium on Computational Geometry (SoCG 2026) |
| Veranstaltung | 42nd International Symposium on Computational Geometry (SoCG 2026), Brunswick, NJ, USA, 02.06.2026 – 05.06.2026 |
| Verlag | Schloss Dagstuhl - Leibniz-Zentrum für Informatik (LZI) |
| Seiten | 1 |
| Serie | 367 |
| Vorab online veröffentlicht am | 27.05.2026 |
| Externe Relationen | Siehe auch |
| Schlagwörter | triangulation, flip distance, parallel flip distance, heuristic, competition, Theory of computation → Computational geometry |
| Nachgewiesen in | Scopus OpenAlex |