Abstract
Given an n-point set in Euclidean space ℝd and an integer k, consider the problem of finding the smallest ball enclosing at least k of the points. In the case of a fixed dimension the problem is polynomial-time solvable but in the general case, when d is not fixed, the complexity status of the problem was not yet known. We prove that the problem is strongly NP-hard and describe an idea of PTAS.
This research is supported by RFBR (projects 12-01-00093, 12-01-33028 and 13-01-91370ST), Presidium RAS (project 227) and IM SBRAS (project 7B).
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
P.K. Agarwal, S. Har-Peled and K.R. Varadarajan, Geometric approximation via coresets, Combinatorial and Computational Geometry, MSRI 52 (2005), 1–30.
A. Aggarwal, H. Imai, N. Katoh and S. Suri, Finding k points with minimum diameter and related problems, J. Algorithms 12 (1991), 38–56.
M. Badoiu and K. L. Clarkson, Smaller core-sets for balls In: “Proc. 14th ACM-SIAM Symposium on Discrete Alg.”, 203, 801–802.
D. Eppstein and J. Erickson, Iterated nearest neighbors and finding minimal polytopes, Disc. Comp. Geom. 11 (1994), 321–350.
M.R. Garey and D.S. Johnson, “Strong” NP-completeness results: motivation, examples, and implications, J. ACM. 25(3) (1978), 499–508.
S. Har-Peled and S. Mazumdar, Fast algorithms for computing the smallest k-enclosing disc Algorithmica 41(3) (2005), 147–157.
A. V. Kel’manov and A. V. Pyatkin, NP-completeness of some problems of choosing a vector subset, J. Applied and Industrial Math. 5(3) (2011), 352–357.
C. H. Papadimitriou, “Computational Complexity”, New-York: Addison-Wesley, 523 pages, 1994.
J.J. Sylvester: A Question in the Geometry of Situation, Quart. J. Math. 1:79, 1857.
V. Vazirani Approximation Algorithms. Berlin: Springer-Verlag, page 71, 2001.
H. Wirth, “Algorithms + Data Structures = Programs”, New Jersey: Prentice Hall, 366 pages, 1976.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2013 Scuola Normale Superiore Pisa
About this paper
Cite this paper
Shenmaier, V. (2013). Complexity and approximation of the smallest k-enclosing ball problem. In: Nešetřil, J., Pellegrini, M. (eds) The Seventh European Conference on Combinatorics, Graph Theory and Applications. CRM Series, vol 16. Edizioni della Normale, Pisa. https://doi.org/10.1007/978-88-7642-475-5_92
Download citation
DOI: https://doi.org/10.1007/978-88-7642-475-5_92
Publisher Name: Edizioni della Normale, Pisa
Print ISBN: 978-88-7642-474-8
Online ISBN: 978-88-7642-475-5
eBook Packages: Mathematics and StatisticsMathematics and Statistics (R0)