Задача о паре ближайших точек ({g;gcg k hgjy Qln'gwon] mkcyt)

Задача о паре ближайших точек — это задача вычислительной геометрии. Дано n точек в метрическом пространстве, нужно найти пару точек с наименьшим расстоянием между ними.

Задача о ближайших точках на евклидовой плоскости^[1] была одной из первых геометрических задач, которая подверглась систематическому изучению со стороны вычислительной сложности геометрических алгоритмов.

Наивный алгоритм нахождения расстояний между всеми парами в пространстве размерности d и выбора среди них наименьшего требует времени O(n²). Оказывается, что задача может быть решена за время $O(n\log n)$ в евклидовом пространстве или L^p пространстве фиксированной размерности d^[2]. В модели вычислений алгебраического дерева решений^[англ.] алгоритм со временем O(n log n) оптимален при сведении от задачи единственности элемента^[англ.]. В вычислительной модели, в которой принимается, что функция floor^[англ.] вычисляема за постоянное время, задача может быть решена за время $O(n\log \log n)$ ^[3]. Если мы позволяем применение рандомизации вместе с функцией floor, задача может быть решена за время O(n)^[4]^[5].

Алгоритм полного перебора

Пара ближайших точек может быть вычислена за время O(n²) путём выполнения полного перебора. Чтобы это сделать, можно вычислить расстояние между всеми n(n − 1) / 2 парами точек, затем выбрать пару с наименьшим расстоянием, как показано ниже.

minDist = infinity
for i = 1 to length(P) - 1
 for j = i + 1 to length(P)
  let p = P[i], q = P[j]
  if dist(p, q) < minDist:
   minDist = dist(p, q)
   closestPair = (p, q)
return closestPair

Планарный случай

Задача может быть решена за время $O(n\log n)$ с помощью рекурсивного подхода «разделяй и властвуй», например, так^[1]:

Сортируем точки согласно их x-координатам;
Разбиваем множество точек на два подмножества равного размера вертикальной прямой $x=x_{mid}$ ;
Решаем задачу рекурсивно на левой и на правой частях. Это приводит к левому минимальному расстоянию $d_{Lmin}$ и правому минимальному расстоянию $d_{Rmin}$ , соответственно;
Находим минимальное расстояние $d_{LRmin}$ среди пар точек, из которых одна точка лежит слева от вертикальной линии, а другая точка лежит справа от прямой;
Конечным ответом будет минимальное значение среди $d_{Lmin}$ , $d_{Rmin}$ и $d_{LRmin}$ .

Оказывается, что шаг 4 может быть выполнен за линейное время. Снова, наивный подход потребовал бы вычисление расстояний для всех пар слева/справа, то есть квадратичное время. Ключевое наблюдение основывается на следующем свойстве разреженности множества точек. Мы уже знаем, что пара ближайших точек не находятся на большем расстоянии, чем $\mathrm {dist} =\min(d_{Lmin},d_{Rmin})$ . Поэтому, для каждой точки p слева от разделяющей прямой мы должны сравнить расстояния до точек, которые лежат в прямоугольнике с размерами (dist, 2 ⋅ dist) как показано на рисунке. И этот прямоугольник может содержать не более шести точек, попарное расстояние между которыми не менее $d_{Rmin}$ . Таким образом, достаточно вычислить на 4-м шаге 6n расстояний^[6]. Рекуррентное отношение для числа шагов может быть записано как $T(n)=2T({\tfrac {n}{2}})+O(n)$ , которое может быть решено с помощью основной теоремы для рекурренции разделяй и властвуй, что даёт $O(n\log n)$ .

Так как пара ближайших точек определяют ребро в триангуляции Делоне и соответствуют двум смежным ячейкам в диаграмме Вороного, пара ближайших точек может быть определена за линейное время, если дана одна из этих двух структур. Вычисление триангуляции Делоне или диаграммы Вороного занимает время $O(n\log n)$ . Эти подходы не эффективны для размерностей d>2, в то время как алгоритм «разделяй и властвуй» может быть обобщён до времени выполнения $O(n\log n)$ для любого постоянного значения размерности d.

Динамическая задача ближайшей пары

Динамическая версия^[англ.] для задачи пары ближайших точек ставится следующим образом:

Если дано динамическое множество объектов, найти алгоритмы и структуры данных для эффективного перевычисления пары ближайших точек каждый раз, когда объект вставляется или удаляется.

Если ограничивающий прямоугольник для всех точек заранее известен и доступна функция floor с постоянным временем работы, то была предложена структура данных с ожидаемой памятью O(n), которая поддерживает ожидаемое время (среднее время) вставки и удаления O(log n) и постоянное время запроса. Если задача модифицирована для модели алгебраического дерева принятия решения, вставки и удаления потребуют среднее время $O(\log ^{2}n)$ ^[7]. Следует отметить, что сложность указанной выше динамической задачи о паре ближайших точек экспоненциально зависит от размерности d, поэтому алгоритм становится менее пригодным для задач высокой размерности.

Алгоритм для динамической задачи пары ближайших точек в пространстве размерности d разработал Сергей Беспамятных в 1998 году^[8]. Точки могут быть вставлены и удалены за время O(logn) на одну точку (в худшем случае).

См. также

Примечания

↑ ¹ ² Shamos, Hoey, 1975, с. 151—162.
↑ Clarkson, 1983.
↑ Fortune, Hopcroft, 1979, с. 20—23.
↑ Khuller, Matias, 1995, с. 34—37.
↑ Richard Lipton. Rabin Flips a Coin (неопр.) (24 сентября 2011). Дата обращения: 19 февраля 2019. Архивировано 16 февраля 2019 года.
↑ Cormen, Leiserson, Rivest, Stein, 2001, с. 957—961 33.4: Finding the closest pair of points..
↑ Golin, Raman, Schwarz, Smid, 1998.
↑ Bespamyatnikh, 1998, с. 175—195.

Литература

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms. — Second Edition. — MIT Press and McGraw-Hill, 2001. — ISBN 0-262-03293-7.
- Перевод: Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. Алгоритмы: построение и анализ. — второе издание. — Москва, Санкт-Петербург, Киев: «Вильямс», 2005. — ISBN 5-8459-0857-4 ББК 32.973.26-018.2.75.
Jon Kleinberg, Éva Tardos. Algorithm Design. — Addison Wesley, 2006.
- Перевод: Джон Клейнберг, Ева Тардос. Алгоритмы. Разработка и применение. — Москва, Санкт-Петербург, Нижний Новгород, Киев: Питер, 2016. — (Классика Computer Science). — ISBN 978-5-496-01545-5 ББК 32.973.2-018.
Michael Ian Shamos, Dan Hoey. Closest-point problems // Proc. 16th Annual IEEE Symposium on Foundations of Computer Science (FOCS). — 1975. — doi:10.1109/SFCS.1975.8.
Fortune S., Hopcroft J.E. A note on Rabin's nearest-neighbor algorithm // Information Processing Letters. — 1979. — Т. 8, вып. 1.
Clarkson K. L. 24th Annual Symposium on Foundations of Computer Science. — 1983.
Khuller S., Matias Y. A simple randomized sieve algorithm for the closest-pair problem // Inf. Comput. — 1995. — Т. 118, вып. 1.
Mordecai Golin, Rajeev Raman, Christian Schwarz, Michiel Smid. Randomized Data Structures For The Dynamic Closest-Pair Problem // SIAM J. Comput.. — 1998. — Т. 26, № 4. Предварительная версия была доложена на симпозиуме «4th Annu. ACM-SIAM Symp. on Discrete Algorithms», 1993, стр. 301—310
Sergey N. Bespamyatnikh. An Optimal Algorithm for Closest-Pair Maintenance // Discrete Comput. Geom. — 1998. — Вып. 19.
UCSB Lecture Notes
rosettacode.org — Closest pair of points implemented in multiple programming languages
Line sweep algorithm for the closest pair problem

[_3262e6d56576de71-1] ¹ ² Shamos, Hoey, 1975, с. 151—162.

[_c4e9fa33ac23293f-2] Clarkson, 1983.

[_3b559b516bedb8c2-3] Fortune, Hopcroft, 1979, с. 20—23.

[_5584b79410a1a376-4] Khuller, Matias, 1995, с. 34—37.

[rl-5] Richard Lipton. Rabin Flips a Coin (неопр.) (24 сентября 2011). Дата обращения: 19 февраля 2019. Архивировано 16 февраля 2019 года.

[_0afbedb799964af4-6] Cormen, Leiserson, Rivest, Stein, 2001, с. 957—961 33.4: Finding the closest pair of points..

[_38ab1739ab6a0145-7] Golin, Raman, Schwarz, Smid, 1998.

[_ab2bea4399c06e86-8] Bespamyatnikh, 1998, с. 175—195.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]