DC Field | Value | Language |
---|---|---|
dc.contributor.author | Kang, B. | - |
dc.contributor.author | Choi, J. | - |
dc.contributor.author | Ahn, H.-K. | - |
dc.date.accessioned | 2021-12-29T09:40:35Z | - |
dc.date.available | 2021-12-29T09:40:35Z | - |
dc.date.created | 2021-10-12 | - |
dc.date.issued | 2021-07 | - |
dc.identifier.issn | 0302-9743 | - |
dc.identifier.uri | https://oasis.postech.ac.kr/handle/2014.oak/108522 | - |
dc.description.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. | - |
dc.language | English | - |
dc.publisher | Springer Science and Business Media Deutschland GmbH | - |
dc.relation.isPartOf | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | - |
dc.title | Intersecting Disks Using Two Congruent Disks | - |
dc.type | Article | - |
dc.identifier.doi | 10.1007/978-3-030-79987-8_28 | - |
dc.type.rims | ART | - |
dc.identifier.bibliographicCitation | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), v.12757 LNCS, pp.400 - 413 | - |
dc.citation.endPage | 413 | - |
dc.citation.startPage | 400 | - |
dc.citation.title | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | - |
dc.citation.volume | 12757 LNCS | - |
dc.contributor.affiliatedAuthor | Kang, B. | - |
dc.contributor.affiliatedAuthor | Ahn, H.-K. | - |
dc.identifier.scopusid | 2-s2.0-85111965107 | - |
dc.description.journalClass | 1 | - |
dc.description.journalClass | 1 | - |
dc.description.isOpenAccess | N | - |
dc.type.docType | Conference Paper | - |
dc.subject.keywordPlus | Artificial intelligence | - |
dc.subject.keywordPlus | Computer science | - |
dc.subject.keywordPlus | Computers | - |
dc.subject.keywordPlus | Deterministic algorithms | - |
dc.subject.keywordPlus | Euclidean | - |
dc.subject.keywordPlus | Expected time | - |
dc.subject.keywordPlus | Optimal algorithm | - |
dc.subject.keywordPlus | Optimal pairs | - |
dc.subject.keywordPlus | Randomized Algorithms | - |
dc.subject.keywordPlus | Combinatorial mathematics | - |
dc.subject.keywordAuthor | Disk covering | - |
dc.subject.keywordAuthor | Euclidean 2-center | - |
dc.subject.keywordAuthor | Parametric search | - |
dc.description.journalRegisteredClass | scopus | - |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.
library@postech.ac.kr Tel: 054-279-2548
Copyrights © by 2017 Pohang University of Science ad Technology All right reserved.