2026-07-21T03:14:49Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23232 2025-10-02T12:43:50Z ddc:004 open_access

Incremental Algorithm and Local Search for Minimum Non-Obtuse Triangulations (CG Challenge) Ahn, Taehoon Lee, Jaegun Kang, Byeonguk Kim, Hwi Triangulation Non-obtuse triangle Steiner point Incremental algorithm Local search 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Taehoon Ahn and Jaegun Lee and Byeonguk Kang and Hwi Kim 2025 Is Part Of LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2025.80 urn:nbn:de:0030-drops-232326 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.80 eng https://creativecommons.org/licenses/by/4.0/legalcode