Abstract:
The smallest $k$-enclosing ball problem is considered: given a finite set of points in the Euclidean space and an integer $k$, find the smallest circle containing at least $k$ of the points. If the space dimension is fixed, the problem is polynomial-time solvable. In the general case, when the dimension belongs to the data input, the complexity status of the problem is still unknown. Strong NP-hardness of the problem is proved and an approximation scheme (PTAS) that solves this problem with an arbitrary relative error $\varepsilon$ in time $O(n^{1/\varepsilon^2+1}d)$, where $n$ is the number of points in the origin set and $d$ is the space dimension, is presented. Bibliogr. 10.
Fulltext:
PDF file (237 kB)