Search Results

Documents authored by Ahn, Taehoon

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}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2024.5
Constrained Two-Line Center Problems

Authors: Taehoon Ahn and Sang Won Bae

Published in: LIPIcs, Volume 322, 35th International Symposium on Algorithms and Computation (ISAAC 2024)

Abstract
Given a set P of n points in the plane, the two-line center problem asks to find two lines that minimize the maximum distance from each point in P to its closer one of the two resulting lines. The currently best algorithm for the problem takes O(n² log² n) time by Jaromczyk and Kowaluk in 1995. In this paper, we present faster algorithms for three variants of the two-line center problem in which the orientations of the resulting lines are constrained. Specifically, our algorithms solve the problem in O(n log n) time when the orientations of both lines are fixed; in O(n log³ n) time when the orientation of one line is fixed; and in O(n² α(n) log n) time when the angle between the two lines is fixed, where α(n) denotes the inverse Ackermann function.
Cite as

Taehoon Ahn and Sang Won Bae. Constrained Two-Line Center Problems. In 35th International Symposium on Algorithms and Computation (ISAAC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 322, pp. 5:1-5:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{ahn_et_al:LIPIcs.ISAAC.2024.5,
  author =	{Ahn, Taehoon and Bae, Sang Won},
  title =	{{Constrained Two-Line Center Problems}},
  booktitle =	{35th International Symposium on Algorithms and Computation (ISAAC 2024)},
  pages =	{5:1--5:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-354-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{322},
  editor =	{Mestre, Juli\'{a}n and Wirth, Anthony},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2024.5},
  URN =		{urn:nbn:de:0030-drops-221327},
  doi =		{10.4230/LIPIcs.ISAAC.2024.5},
  annote =	{Keywords: two-line center problem, geometric location problem, geometric optimization}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2022.51
Farthest-Point Voronoi Diagrams in the Presence of Rectangular Obstacles

Authors: Mincheol Kim, Chanyang Seo, Taehoon Ahn, and Hee-Kap Ahn

Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)

Abstract
We present an algorithm to compute the geodesic L₁ farthest-point Voronoi diagram of m point sites in the presence of n rectangular obstacles in the plane. It takes O(nm+n log n + mlog m) construction time using O(nm) space. This is the first optimal algorithm for constructing the farthest-point Voronoi diagram in the presence of obstacles. We can construct a data structure in the same construction time and space that answers a farthest-neighbor query in O(log(n+m)) time.
Cite as

Mincheol Kim, Chanyang Seo, Taehoon Ahn, and Hee-Kap Ahn. Farthest-Point Voronoi Diagrams in the Presence of Rectangular Obstacles. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 51:1-51:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{kim_et_al:LIPIcs.SoCG.2022.51,
  author =	{Kim, Mincheol and Seo, Chanyang and Ahn, Taehoon and Ahn, Hee-Kap},
  title =	{{Farthest-Point Voronoi Diagrams in the Presence of Rectangular Obstacles}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{51:1--51:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-227-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{224},
  editor =	{Goaoc, Xavier and Kerber, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.51},
  URN =		{urn:nbn:de:0030-drops-160596},
  doi =		{10.4230/LIPIcs.SoCG.2022.51},
  annote =	{Keywords: Geodesic distance, L₁ metric, farthest-point Voronoi diagram}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact