TY - JOUR

T1 - The aligned K-center problem

AU - Braß, Peter

AU - Knauer, Christian

AU - Na, Hyeonsuk

AU - Shin, Chansu

AU - Vigneron, Antoine E.

N1 - KAUST Repository Item: Exported on 2020-10-01
Acknowledgements: Author for correspondence; Supported by Korean Research Foundation Grant (KRF-2007-531-D00018).Supported by National Research Foundation of Korea (NRF) grant funded by the Korea government (MEST) (No. 2010-0016416), and the HUFS Research Fund.

PY - 2011/11/20

Y1 - 2011/11/20

N2 - In this paper we study several instances of the aligned k-center problem where the goal is, given a set of points S in the plane and a parameter k ≥ 1, to find k disks with centers on a line ℓ such that their union covers S and the maximum radius of the disks is minimized. This problem is a constrained version of the well-known k-center problem in which the centers are constrained to lie in a particular region such as a segment, a line, or a polygon. We first consider the simplest version of the problem where the line ℓ is given in advance; we can solve this problem in time O(n log2 n). In the case where only the direction of ℓ is fixed, we give an O(n2 log 2 n)-time algorithm. When ℓ is an arbitrary line, we give a randomized algorithm with expected running time O(n4 log2 n). Then we present (1+ε)-approximation algorithms for these three problems. When we denote T(k, ε) = (k/ε2+(k/ε) log k) log(1/ε), these algorithms run in O(n log k + T(k, ε)) time, O(n log k + T(k, ε)/ε) time, and O(n log k + T(k, ε)/ε2) time, respectively. For k = O(n1/3/log n), we also give randomized algorithms with expected running times O(n + (k/ε2) log(1/ε)), O(n+(k/ε3) log(1/ε)), and O(n + (k/ε4) log(1/ε)), respectively. © 2011 World Scientific Publishing Company.

AB - In this paper we study several instances of the aligned k-center problem where the goal is, given a set of points S in the plane and a parameter k ≥ 1, to find k disks with centers on a line ℓ such that their union covers S and the maximum radius of the disks is minimized. This problem is a constrained version of the well-known k-center problem in which the centers are constrained to lie in a particular region such as a segment, a line, or a polygon. We first consider the simplest version of the problem where the line ℓ is given in advance; we can solve this problem in time O(n log2 n). In the case where only the direction of ℓ is fixed, we give an O(n2 log 2 n)-time algorithm. When ℓ is an arbitrary line, we give a randomized algorithm with expected running time O(n4 log2 n). Then we present (1+ε)-approximation algorithms for these three problems. When we denote T(k, ε) = (k/ε2+(k/ε) log k) log(1/ε), these algorithms run in O(n log k + T(k, ε)) time, O(n log k + T(k, ε)/ε) time, and O(n log k + T(k, ε)/ε2) time, respectively. For k = O(n1/3/log n), we also give randomized algorithms with expected running times O(n + (k/ε2) log(1/ε)), O(n+(k/ε3) log(1/ε)), and O(n + (k/ε4) log(1/ε)), respectively. © 2011 World Scientific Publishing Company.

UR - http://hdl.handle.net/10754/561744

UR - https://www.worldscientific.com/doi/abs/10.1142/S0218195911003597

UR - http://www.scopus.com/inward/record.url?scp=79954483509&partnerID=8YFLogxK

U2 - 10.1142/S0218195911003597

DO - 10.1142/S0218195911003597

M3 - Article

SN - 0218-1959

VL - 21

SP - 157

EP - 178

JO - International Journal of Computational Geometry & Applications

JF - International Journal of Computational Geometry & Applications

IS - 02

ER -