THE ALIGNED K-CENTER PROBLEM.

In this paper we study several instances of the alignedk-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 log² n). In the case where only the direction of ℓ is fixed, we give an O(n²log² n)-time algorithm. When ℓ is an arbitrary line, we give a randomized algorithm with expected running time O(n⁴log² n). Then we present (1+ε)-approximation algorithms for these three problems. When we denote T(k, ε) = (k/ε²+(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, ε)/ε²) time, respectively. For k = O(n^1/3/log n), we also give randomized algorithms with expected running times O(n + (k/ε²) log(1/ε)), O(n+(k/ε³) log(1/ε)), and O(n + (k/ε⁴) log(1/ε)), respectively. [ABSTRACT FROM AUTHOR]