Том 20, номер 1, 2013 г., Стр. 93-99
УДК 519.176
Шенмайер В. В.
Задача о минимальном шаре, охватывающем k точек
Аннотация:
Рассматривается задача поиска шара минимального радиуса, охватывающего не менее$k$ точек из заданного конечного множества в евклидовом пространстве. В случае фиксированной размерности пространства задача полиномиально разрешима, но в общем случае сложностной статус задачи до настоящего времени не был установлен. Доказано, что задача NP-трудна в сильном смысле, а также получена полиномиальная аппроксимационная схема (PTAS), позволяющая решать задачу с произвольной относительной погрешностью$\varepsilon$ за время$O(n^{1/\varepsilon^2+1}d)$ , где$n$ – мощность исходного множества,$d$ – размерность пространства.
Библиогр. 10.
Ключевые слова: минимальный охватывающий шар, кластерный анализ, аппроксимационная схема, приближённый алгоритм.
Шенмайер Владимир Владимирович 1
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
е-mail: shenmaier@mail.ru
Статья поступила 26 июля 2012 г.
Литература
[1] Кельманов А. В., Пяткин А. В. NP-полнота некоторых задач выбора подмножества векторов // Дискрет. анализ и исслед. операций. — 2010. — T. 17, №5. — С. 37—45.
[2] Aggarwal A., Imai H., Katoh N., Suri S. Finding k points with minimum diameter and related problems // J. Algorithms. — 1991. — Vol. 12. — P. 38– 56.
[3] Badoiu M., Clarkson K. L. Smaller core-sets for balls // Proc. 14th ACMSIAM Symposium on Discrete Alg. (Baltimore, January 12–14, 2003).— Philadelphia: SIAM, 2003.—P. 801–802.
[4] Eppstein D., Erickson J. Iterated nearest neighbors and finding minimal polytopes // Discrete Comput. Geom. — 1994. — Vol. 11. — P. 321–350.
[5] Garey M. R., Johnson D. S. “Strong” NP-completeness results: motivation, examples, and implications // J. ACM. — 1978. — Vol. 25, N 3. — P. 499—508.
[6] Har-Peled S., Mazumdar S. Fast algorithms for computing the smallest k-enclosing disc // Algorithmica. — 2005. — Vol. 41, N3. — P. 147–157.
[7] Papadimitriou C. H. Computational complexity. — New York: Addison-Wesley, 1994. — 523 p.
[8] Sylvester J. J. A question in the geometry of situation // Quart. J. Math. — 1857. — Vol. 1. — P. 79.
[9] Vazirani V. Approximation algorithms. — Berlin: Springer-Verl., 2001. — 71 p.
[10] Wirth Н. Algorithms + data structures = programs. — New Jersey: Prentice Hall, 1976. — 366 p.
