Algorithms for Halfplane Coverage and Related Problems.
Saved in:
| Title: | Algorithms for Halfplane Coverage and Related Problems. |
|---|---|
| Authors: | Wang, Haitao1 (AUTHOR) haitao.wang@utah.edu, Xue, Jie2 (AUTHOR) jiexue@nyu.edu |
| Source: | Discrete & Computational Geometry. Jun2026, Vol. 75 Issue 4, p1073-1104. 32p. |
| Subjects: | Algorithms, Computational geometry, Geometric approach, Polygons, Mathematical optimization, Time complexity |
| Abstract: | Given in the plane a set of points and a set of halfplanes, we consider the problem of computing a smallest subset of halfplanes whose union covers all points. In this paper, we present an O (n 4 / 3 log 5 / 3 n log O (1) log n) -time algorithm for the problem, where n is the total number of all points and halfplanes. This improves the previously best algorithm of n 10 / 3 2 O (log ∗ n) time by roughly a quadratic factor. For the special case where all halfplanes are lower ones, our algorithm runs in O (n log n) time, which improves the previously best algorithm of n 4 / 3 2 O (log ∗ n) time and matches an Ω (n log n) lower bound. Further, our techniques can be extended to solve a star-shaped polygon coverage problem in O (n log n) time, which in turn leads to an O (n log n) -time algorithm for computing an instance-optimal ε -kernel of a set of n points in the plane. Agarwal and Har-Peled presented an O (n k log n) -time algorithm for this problem in SoCG 2023, where k is the size of the ε -kernel; they also raised an open question whether the problem can be solved in O (n log n) time. Our result thus answers the open question affirmatively. [ABSTRACT FROM AUTHOR] |
| Copyright of Discrete & Computational Geometry is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
|
Full text is not displayed to guests.
Login for full access.
|
|
| Abstract: | Given in the plane a set of points and a set of halfplanes, we consider the problem of computing a smallest subset of halfplanes whose union covers all points. In this paper, we present an O (n 4 / 3 log 5 / 3 n log O (1) log n) -time algorithm for the problem, where n is the total number of all points and halfplanes. This improves the previously best algorithm of n 10 / 3 2 O (log ∗ n) time by roughly a quadratic factor. For the special case where all halfplanes are lower ones, our algorithm runs in O (n log n) time, which improves the previously best algorithm of n 4 / 3 2 O (log ∗ n) time and matches an Ω (n log n) lower bound. Further, our techniques can be extended to solve a star-shaped polygon coverage problem in O (n log n) time, which in turn leads to an O (n log n) -time algorithm for computing an instance-optimal ε -kernel of a set of n points in the plane. Agarwal and Har-Peled presented an O (n k log n) -time algorithm for this problem in SoCG 2023, where k is the size of the ε -kernel; they also raised an open question whether the problem can be solved in O (n log n) time. Our result thus answers the open question affirmatively. [ABSTRACT FROM AUTHOR] |
|---|---|
| ISSN: | 01795376 |
| DOI: | 10.1007/s00454-024-00709-y |
