Shadoks Approach to Parallel Reconfiguration of Triangulations
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866918401789657088 |
|---|---|
| author | da Fonseca, Guilherme D. Feschet, Fabien Gerard, Yan |
| author_facet | da Fonseca, Guilherme D. Feschet, Fabien Gerard, Yan |
| contents | We describe the methods used by Team Shadoks to win the CG:SHOP 2026 Challenge on parallel reconfiguration of planar triangulations. An instance is a collection of triangulations of a common point set. We must select a center triangulation and find short parallel-flip paths from each input triangulation to the center, minimizing the sum of path lengths. Our approach combines exact methods based on SAT with several greedy heuristics, and also makes use of SAT and MaxSAT for solution improvement. We present a SAT encoding for bounded-length paths and a global formulation for fixed path-length vectors. We discuss how these components interact in practice and summarize the performance of our solvers on the benchmark instances. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_21293 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Shadoks Approach to Parallel Reconfiguration of Triangulations da Fonseca, Guilherme D. Feschet, Fabien Gerard, Yan Computational Geometry We describe the methods used by Team Shadoks to win the CG:SHOP 2026 Challenge on parallel reconfiguration of planar triangulations. An instance is a collection of triangulations of a common point set. We must select a center triangulation and find short parallel-flip paths from each input triangulation to the center, minimizing the sum of path lengths. Our approach combines exact methods based on SAT with several greedy heuristics, and also makes use of SAT and MaxSAT for solution improvement. We present a SAT encoding for bounded-length paths and a global formulation for fixed path-length vectors. We discuss how these components interact in practice and summarize the performance of our solvers on the benchmark instances. |
| title | Shadoks Approach to Parallel Reconfiguration of Triangulations |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2603.21293 |