Computing k-centers of uncertain points on a real line

In this paper we study the one-dimensional k-center problem on uncertain points. Given a set of n uncertain points each represented by a segment of its appearance on a real line, the k-center problem is computing a set Q of k points (centers) on the line to minimize the maximum of (weighted) minimum or maximum possible distances of uncertain points to their closest centers. We present O(nlog⁡n)-time and O(n)-time algorithms respectively for this problem and the unweighted case.