WikiSort.ru - Не сортированное

ПОИСК ПО САЙТУ | о проекте
Пара ближайших точек выделена красным цветом

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

Дано n точек в метрическом пространстве, найти пару точек с наименьшим расстоянием между ними.

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

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

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

Пара ближайших точек может быть вычислена за время O(n2) путём выполнения полного перебора. Чтобы это сделать, можно вычислить расстояние между всеми 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

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

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

  1. Сортируем точки согласно их x-координатам.
  2. Разбиваем множество точек на два подмножества равного размера вертикальной прямой .
  3. Решаем задачу рекурсивно на левой и на правой частях. Это приводит к левому минимальному расстоянию и правому минимальному расстоянию , соответственно.
  4. Находим минимальное расстояние среди пар точек, из которых одна точка лежит слева от вертикальной линии, а другая точка лежит справа от прямой.
  5. Конечным ответом будет минимальное значение среди , и .
Divide-and-conquer: sparse box observation

Оказывается, что шаг 4 может быть выполнен за линейное время. Снова, наивный подход потребовал бы вычисление расстояний для всех пар слева/справа, то есть квадратичное время. Ключевое наблюдение основывается на следующем свойстве разреженности множества точек. Мы уже знаем, что пара ближайших точек не находятся на большем расстоянии, чем . Поэтому, для каждой точки p слева от разделяющей прямой мы должны сравнить расстояния до точек, которые лежат в прямоугольнике с размерами (dist, 2 ⋅ dist) как показано на рисунке. И этот прямоугольник может содержать не более шести точек, попарное расстояние между которыми не менее . Таким образом, достаточно вычислить на 4-м шаге 6n расстояний[6]. Рекуррентное отношение для числа шагов может быть записано как , которое может быть решено с помощью основной теоремы для рекурренции разделяй и властвуй, что даёт .

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

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

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

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

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

См. также

Примечания

  1. 1 2 Shamos, Hoey, 1972, с. 151-162.
  2. Clarkson, 1983.
  3. Fortune, Hopcroft, 1979, с. 20-23.
  4. Khuller, Matias, 1995, с. 34-37.
  5. Richard Lipton. Rabin Flips a Coin (24 September 2011).
  6. Cormen, Leiserson, Rivest, Stein, 2001, с. 957-961 33.4: Finding the closest pair of points..
  7. Golin, Raman, Schwarz, Smid, 1998.
  8. Bespamyatnikh, 1998, с. 175-195.

    Литература

    Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".

    Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.

    Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .




    Текст в блоке "Читать" взят с сайта "Википедия" и доступен по лицензии Creative Commons Attribution-ShareAlike; в отдельных случаях могут действовать дополнительные условия.

    Другой контент может иметь иную лицензию. Перед использованием материалов сайта WikiSort.ru внимательно изучите правила лицензирования конкретных элементов наполнения сайта.

    2019-2025
    WikiSort.ru - проект по пересортировке и дополнению контента Википедии