Intersecting Disks Using Two Congruent Disks
SCOPUS
- Title
- Intersecting Disks Using Two Congruent Disks
- Authors
- Kang, B.; Choi, J.; Ahn, H.-K.
- Date Issued
- 2021-07
- Publisher
- Springer Science and Business Media Deutschland GmbH
- Abstract
- We consider the Euclidean 2-center problem for a set of n disks in the plane: find two smallest congruent disks such that every disk in the set intersects at least one of the two congruent disks. We present a deterministic algorithm for the problem that returns an optimal pair of congruent disks in O(n2log3n / log log n) time. We also present a randomized algorithm with O(n2log2n / log log n) expected time. These results improve the previously best deterministic and randomized algorithms, making a step closer to the optimal algorithms for the problem. We show that the same algorithms also work for the 2-piercing problem and the restricted 2-covering problem on disks. ? 2021, Springer Nature Switzerland AG.
- URI
- https://oasis.postech.ac.kr/handle/2014.oak/108522
- DOI
- 10.1007/978-3-030-79987-8_28
- ISSN
- 0302-9743
- Article Type
- Article
- Citation
- Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 12757 LNCS, page. 400 - 413, 2021-07
- 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.