Approximation Algorithms for a k-Line Center

Given a set P of n points in ℝd and an integer k ≥ 1, let w^* denote the minimum value so that P can be covered by k congruent cylinders of radius w^*. We describe a randomized algorithm that, given P and an ε > 0, computes k cylinders of radius (1 + ε) w^* that cover P. The expected running time of the algorithm is O(n log n), with the constant of proportionality depending onk, d, and ε. We first show that there exists a small”certificate” Q ⫅ P, whose size does not depend on n,such that for any k congruent cylinders that cover Q, an expansion ofthese cylinders by a factor of (1 + ε) covers P. We then use a well-known scheme based on sampling and iterated re-weighting for computing the cylinders.