Maximum Coverage by k Lines
SCIE
- Title
- Maximum Coverage by k Lines
- Authors
- CHUNG, CHAE YOON; Vigneron, Antoine; Ahn, Hee-Kap
- Date Issued
- 2024-02
- Publisher
- Multidisciplinary Digital Publishing Institute (MDPI)
- Abstract
- Given a set of n disks in the plane, we study the problem of finding k lines that together intersect the maximum number of input disks. We consider three variants of this problem with the following constraints on the solution: (1) no constraint on the lines, (2) the k lines should be parallel and (3) the k lines should pass through a common point. For k=2, we give O(n3logn)-time algorithms for all three cases. For any fixed k≥3, we give an O(n3k/2)-time algorithm for (1). For variants (2) and (3), the running times of our algorithms vary from O(n4) to O(n6).
- URI
- https://oasis.postech.ac.kr/handle/2014.oak/120808
- DOI
- 10.3390/sym16020206
- ISSN
- 2073-8994
- Article Type
- Article
- Citation
- Symmetry, vol. 16, no. 2, page. 206, 2024-02
- Files in This Item:
- There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.