The smallest $k$-enclosing ball problem
Diskretnyj analiz i issledovanie operacij, Tome 20 (2013) no. 1, pp. 93-99
Voir la notice de l'article provenant de la source Math-Net.Ru
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.
Keywords:
smallest enclosing ball, $k$-enclosing ball, cluster analysis, approximation scheme, approximation algorithm.
@article{DA_2013_20_1_a7,
author = {V. V. Shenmaier},
title = {The smallest $k$-enclosing ball problem},
journal = {Diskretnyj analiz i issledovanie operacij},
pages = {93--99},
publisher = {mathdoc},
volume = {20},
number = {1},
year = {2013},
language = {ru},
url = {http://geodesic.mathdoc.fr/item/DA_2013_20_1_a7/}
}
V. V. Shenmaier. The smallest $k$-enclosing ball problem. Diskretnyj analiz i issledovanie operacij, Tome 20 (2013) no. 1, pp. 93-99. http://geodesic.mathdoc.fr/item/DA_2013_20_1_a7/