Том 23, номер 4, 2016 г., Стр. 102-115

УДК 519.176
Шенмайер В. В.
Решение некоторых задач поиска подмножества векторов с использованием диаграмм Вороного

Аннотация:
Предлагается общий подход к решению некоторых задач поиска подмножества векторов в евклидовом пространстве, основанный на использовании диаграмм Вороного высших порядков. В случае фиксированной размерности пространства данный подход
позволяет находить оптимальные решения этих задач за полиномиальное время, меньшее, чем время работы известных ранее алгоритмов.
Ил. 1, библиогр. 16.

Ключевые слова: вычислительная геометрия, поиск подмножества векторов, евклидово пространство, диаграммa Вороного, полиномиальный алгоритм.

DOI: 10.17377/daio.2016.23.526

Шенмайер Владимир Владимирович ¹
1. Институт математики им. С. Л. Соболева,
пр. Коптюга, 4, 630090 Новосибирск, Россия
е-mail: shenmaier@mail.ru

Статья поступила 20 мая 2016 г.
Исправленный вариант — 15 июня 2016 г.

Литература

[1] Бабурин А. Е., Гимади Э. Х., Глебов Н. И., Пяткин А. В. Задача отыскания подмножества векторов с максимальным суммарным весом // Дискрет. анализ и исслед. операций. Сер. 2. 2007. Т. 14, № 1. С. 32–42.

[2] Бабурин А. Е., Пяткин А. В. О полиномиальных алгоритмах решения одной задачи суммирования векторов // Дискрет. анализ и исслед. операций. Сер. 1. 2006. Т. 13, № 2. С. 3–10.

[3] Гимади Э. Х., Кельманов А. В., Кельманова М. А., Хамидуллин С. А. Апостериорное обнаружение в числовой последовательности квазипериодического фрагмента при заданном числе повторов // Сиб.
журн. индустр. математики. 2006. Т. 9, № 1. С. 55–74.

[4] Гимади Э. Х., Пяткин А. В., Рыков И. А. О полиномиальной разрешимости некоторых задач выбора подмножества векторов в евклидовом пространстве фиксированной размерности // Дискрет. анализ и исслед. операций. 2008. Т. 15, № 6. С. 11–19.

[5] Долгушев А. В., Кельманов А. В. Приближённый алгоритм решения одной задачи кластерного анализа // Дискрет. анализ и исслед. операций. 2011. Т. 18, № 2. С. 29–40.

[6] Долгушев А. В., Кельманов А. В., Шенмайер В. В. Полиномиальная аппроксимационная схема для одной задачи разбиения конечного множества на два кластера // Тр. Ин-та математики и механики УрО РАН, 2015. Т. 21, № 3. С. 100–109.

[7] Кельманов А. В., Пяткин А. В. Об одном варианте задачи выбора подмножества векторов // Дискрет. анализ и исслед. операций. 2008. T. 15, № 5. С. 20–34.

[8] Кельманов А. В., Пяткин А. В. NP-полнота некоторых задач выбора подмножества векторов // Дискрет. анализ и исслед. операций. 2010. T. 17, № 5. С. 37–45.

[9] Кельманов А. В., Романченко С. М. FPTAS для одной задачи поиска подмножества векторов // Дискрет. анализ и исслед. операций. 2014. Т. 21, № 3. С. 41–52.

[10] Шенмайер В. В. Аппроксимационная схема для одной задачи поиска подмножества векторов // Дискрет. анализ и исслед. операций. 2012. Т. 19, № 2. С. 92–100.

[11] Aggarwal A., Imai H., Katoh N., Suri S. Finding k points with minimum diameter and related problems // J. Algorithms. 1991. Vol. 12, No. 1. P. 38–56.

[12] Aronov B., Har-Peled S. On approximating the depth and related problems // SIAM J. Computing. 2008. Vol. 38, No. 3. P. 899–921.

[13] Aurenhammer F., Klein R. Voronoi diagrams // Handbook of computational geometry (J.-R. Sack, J. Urrutia, ed.). Amsterdam: Elsevier, 2000. P. 201–290.

[14] Edelsbrunner H., O’Rourke J., Seidel R. Constructing arrangements of lines and hyperplanes with applications // SIAM J. Computing. 1986. Vol. 15, No. 2. P. 341–363.

[15] Johnson D. S., Preparata F. P. The densest hemisphere problem // Theor. Comput. Sci. 1978. Vol. 6, No. 1. P. 93–107.

[16] Shamos M. I., Hoey D. Closest-point problems // Proc. 16th IEEE Annu. Symp. Found. Comput. Sci. (Berkeley, Oct. 13–15, 1975). Piscaway: IEEE, 1975. P. 151–162.