Smallest enclosing ball for probabilistic data

Abstract

This paper deals with computing the smallest enclosing ball of a set of points subject to probabilistic data. In our setting, any of the n points may not or may occur at one of finitely many locations, following its own discrete probability distribution. The objective is therefore considered to be a random variable and we aim at finding a center minimizing the expected maximum distance to the points according to their distributions. Our main contribution presented in this paper is the first polynomial time (1 + ϵ)-approximation algorithm for the probabilistic smallest enclosing ball problem with extensions to the streaming setting.