Assigning weights to minimize the covering radius in the plane
SCIE
SCOPUS
- Title
- Assigning weights to minimize the covering radius in the plane
- Authors
- Oh, E.; Ahn, H.-K.
- Date Issued
- 2019-08
- Publisher
- Elsevier BV
- Abstract
- Given a set P of n points in the plane and a multiset W of k weights with k <= n, we assign each weight in W to a distinct point in P to minimize the maximum weighted distance from the weighted center of P to any point in P. In this paper, we present an algorithm which takes O(k(2)n(2) log(3)n) time for the problem. We also consider the case that all weights in W are at most 1, and present an O(k(5)n log(3)k + kn log(3)n)-time algorithm. For a constant k, it takes only O(n log(3)n) time, which is near linear. (C) 2019 Elsevier B.V. All rights reserved.
- URI
- https://oasis.postech.ac.kr/handle/2014.oak/100365
- DOI
- 10.1016/j.comgeo.2018.10.007
- ISSN
- 0925-7721
- Article Type
- Article
- Citation
- Computational Geometry: Theory and Applications, vol. 81, page. 22 - 32, 2019-08
- 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.