  In this paper, we consider a facility location problem to find a minimum-sum
coverage of n points by disks centered at a fixed line. The cost of a disk with
radius r has a form of a non-decreasing function f(r) = r^a for any a >= 1. The
goal is to find a set of disks under Lp metric such that the disks are centered
on the x-axis, their union covers n points, and the sum of the cost of the
disks is minimized. Alt et al. [1] presented an algorithm in O(n^4 log n) time
for any a > 1 under any Lp metric. We present a faster algorithm for this
problem in O(n^2 log n) time for any a > 1 and any Lp metric.

Computational Geometry