The problem of a minimal ball enclosing k points
Vladimir Shenmaier · Journal of Applied and Industrial Mathematics · 2013
Under study is the problem of finding a ball of minimal radius enclosing at least k points of a given finite set in a Euclidean space. In the case of a fixed dimension of the space this problem is polynomially solvable, but in general its complexity has not been previously determined. We prove that the problem is NP-hard in the strong sense and obtain a polynomial-time approximation scheme (PTAS) that enables us to solve the problem with an arbitrary relative error ɛ in time $O(n^{1/\varepsilon ^2 + 1} d)$ , where n is the cardinality of the original set and d is the space dimension.