The 2-center problem in three dimensions (Q1947989)

This paper deals with the so-called 2-center problem in \(\mathbb{R}^{3}\), i.e., the problem to find two congruent balls of minimum radius whose union covers a set of the given \(n\) points in \(\mathbb{R}^{3}\). The authors present a randomized algorithm, which is composed of a decision problem and a randomized optimization procedure. They claim that the proposed algorithm is near by quadratic unless the radius of the 2-center balls is not too close to the radius of the smallest enclosing ball. The authors also mention some open issues on this problem.