DROPS

Document

DOI: 10.4230/LIPIcs.ISAAC.2025.21

Covering Weighted Points Using Unit Squares

Authors: Chaeyoon Chung, Jaegun Lee, and Hee-Kap Ahn

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract

Given a set of n points in d-dimensional space, each assigned a positive weight, we study the problem of finding k axis-parallel unit hypercubes that maximize the total weight of the points contained in their union. In this paper, we present both exact and (1 - ε)-approximation algorithms for the case of k = 2. We present an exact algorithm that runs in O(n²) time in the plane, improving the previous O(n² log² n)-time result. This algorithm generalizes to higher dimensions and larger k in O(n^{dk/2}) time for fixed d and k. We also present a (1 - ε)-approximation algorithm that runs in O(n log min{n, 1/ε} + 1/ε³) time for k = 2 in the plane, improving the best known result. Our approximation algorithm also extends to higher dimensions.

Cite as

Chaeyoon Chung, Jaegun Lee, and Hee-Kap Ahn. Covering Weighted Points Using Unit Squares. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 21:1-21:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chung_et_al:LIPIcs.ISAAC.2025.21,
  author =	{Chung, Chaeyoon and Lee, Jaegun and Ahn, Hee-Kap},
  title =	{{Covering Weighted Points Using Unit Squares}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{21:1--21:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.21},
  URN =		{urn:nbn:de:0030-drops-249292},
  doi =		{10.4230/LIPIcs.ISAAC.2025.21},
  annote =	{Keywords: Maximum coverage, Unit squares, Approximation algorithms}
}

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 Lee, Jaegun

Covering Weighted Points Using Unit Squares

Abstract

Cite as

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

Abstract

Cite as

Thanks for your feedback!

Could not send message