Volume 20, No 1, 2013, P. 9399
UDC 519.176
Shenmaier V. V.
The smallest kenclosing ball problem
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 polynomialtime solvable. In the general case, when the dimension belongs to the data input, the complexity status of the problem is still unknown. Strong NPhardness 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.
Keywords: smallest enclosing ball, kenclosing ball, cluster analysis, approximation scheme, approximation algorithm.
Shenmaier Vladimir Vladimirovich ^{1}
1. S. L. Sobolev Institute of Mathematics, SB RAS,
4 Acad. Koptyug Ave., 630090 Novosibirsk, Russia
email: shenmaier@mail.ru
