DROPS

Document

CG Challenge

DOI: 10.4230/LIPIcs.SoCG.2026.108

CG#Hunters Approach to Central Triangulation Under Parallel Flip Operations (CG Challenge)

Authors: Jaegun Lee, Seokyun Kang, Hyeonseok Lee, Hyeyun Yang, and Taehoon Ahn

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

Abstract

In the CG:SHOP 2026 Challenge, the goal is to compute a central triangulation for a given set of triangulations on the same point set while minimizing the sum of parallel flip distances. To address the problem, our team (CG#Hunters) constructs an initial solution by iteratively applying parallel flips to reduce the total number of crossings between the triangulations until none remain. To optimize these solutions, we shorten the paths by using a score-based greedy edge selection and refine the central triangulation via a large scale neighborhood search. Additionally, a representative-set-based approach is utilized to efficiently handle large instances. With these combined approaches, we achieved third place by successfully computing central triangulations with sufficiently short parallel flip paths for all 250 instances.

Cite as

Jaegun Lee, Seokyun Kang, Hyeonseok Lee, Hyeyun Yang, and Taehoon Ahn. CG#Hunters Approach to Central Triangulation Under Parallel Flip Operations (CG Challenge). In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 108:1-108:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{lee_et_al:LIPIcs.SoCG.2026.108,
  author =	{Lee, Jaegun and Kang, Seokyun and Lee, Hyeonseok and Yang, Hyeyun and Ahn, Taehoon},
  title =	{{CG#Hunters Approach to Central Triangulation Under Parallel Flip Operations}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{108:1--108:8},
  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.108},
  URN =		{urn:nbn:de:0030-drops-259147},
  doi =		{10.4230/LIPIcs.SoCG.2026.108},
  annote =	{Keywords: Central triangulation, Parallel flip operations, Crossing number, Large scale neighborhood search, Representative set}
}

Search Results

Documents authored by Lee, Hyeonseok

CG#Hunters Approach to Central Triangulation Under Parallel Flip Operations (CG Challenge)

Abstract

Cite as

Thanks for your feedback!

Could not send message