DROPS

Document

CG Challenge

DOI: 10.4230/LIPIcs.SoCG.2025.80

Incremental Algorithm and Local Search for Minimum Non-Obtuse Triangulations (CG Challenge)

Authors: Taehoon Ahn, Jaegun Lee, Byeonguk Kang, and Hwi Kim

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract

In this year’s CG challenge, the task was to compute a non-obtuse triangulation of given planar regions while minimizing the number of Steiner points. Our team (Gwamegi) used two approaches. The first approach incrementally adds Steiner points on the grid defined by the input points in the planar regions, while maintaining a Delaunay triangulation. The second approach is an iterated local search, which runs insertion and deletion steps alternatingly. In the insertion step, we add a new Steiner point inside a maximal convex subpolygon in the current triangulation. In the deletion step, we remove a number of Steiner points packed in a small region. We use both our approaches to obtain non-obtuse triangulations for all 150 instances. We use our second approach to reduce the number of Steiner points from the non-obtuse triangulations. We have successfully computed non-obtuse triangulations using a sufficiently small number of Steiner points for all instances.

Cite as

Taehoon Ahn, Jaegun Lee, Byeonguk Kang, and Hwi Kim. Incremental Algorithm and Local Search for Minimum Non-Obtuse Triangulations (CG Challenge). In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 80:1-80:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{ahn_et_al:LIPIcs.SoCG.2025.80,
  author =	{Ahn, Taehoon and Lee, Jaegun and Kang, Byeonguk and Kim, Hwi},
  title =	{{Incremental Algorithm and Local Search for Minimum Non-Obtuse Triangulations}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{80:1--80:8},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.80},
  URN =		{urn:nbn:de:0030-drops-232326},
  doi =		{10.4230/LIPIcs.SoCG.2025.80},
  annote =	{Keywords: Triangulation, Non-obtuse triangle, Steiner point, Incremental algorithm, Local search}
}

Search Results

Documents authored by Kim, Hwi

Incremental Algorithm and Local Search for Minimum Non-Obtuse Triangulations (CG Challenge)

Abstract

Cite as

Thanks for your feedback!

Could not send message