2026-07-20T10:52:11Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24929 2026-02-09T08:02:12Z ddc:004 open_access

Covering Weighted Points Using Unit Squares Chung, Chaeyoon Lee, Jaegun Ahn, Hee-Kap Maximum coverage Unit squares Approximation algorithms 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Chaeyoon Chung and Jaegun Lee and Hee-Kap Ahn 2025 Is Part Of LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2025.21 urn:nbn:de:0030-drops-249292 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.21 eng https://creativecommons.org/licenses/by/4.0/legalcode