Алгоритм поиска точек, наиболее удаленных друг от друга - лучше, чем O (n ^ 2)?

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

Алгоритм, который я использую, чтобы найти две точки, наиболее удаленные друг от друга, однако, проблематичен для больших наборов точек, поскольку он O(n^2); псевдокод (расстояния, которые уже были рассчитаны, пропущены):

 for each point in points:
     for each other point in points:
         if distance between point and other point > max
             max = distance between point and other point

Есть ли что-то быстрее?

Ответы

Ответ 1

Если вам нужна шкала, а не точные точки, вы можете сделать это в O (n) времени с некоторым запасом погрешности. Подумайте о простом случае создания ограничивающей рамки. Вычислите минимальное значение x из всех точек, максимум x, минимум y и максимум y. Эти четыре числа дают вам максимальную ограничительную рамку вокруг ваших точек с максимальной ошибкой 1 - (1/sqrt (2)) около 30%. Вы можете уменьшить это, добавив больше сторон на ваш квадрат. Подумайте о случае восьмиугольника. Чтобы рассчитать минимальные и максимальные значения для других сторон, вы должны повернуть свою систему координат.

Ошибка против времени выполнения ломается следующим образом.

форма - время выполнения - максимальная ошибка

square - 2N - 30%
восьмиугольник - 4N - 16%
16 сторон - 8N - 4%
32 стороны - 16N - 1%

Здесь уравнение для ошибки max, с которой я столкнулся.

angle = 180 / sides
max_error = (1 / cos angle) - cos angle

Сообщите мне, если я должен добавить диаграмму, объясняющую это.

Ответ 2

Ниже приведено сравнение алгоритмов линейного времени среднего значения (для диаметра конечного множества) в более ясном свете, а также проблемы многомерной и плоской геометрии контраста.

В 1983 году Мегиддо дал детерминированный алгоритм линейного времени для наименьший окружающий круг (или сфера в более высоких измерениях).

В общем положении окружная окружность будет иметь две или три точки на своей границе, и, таким образом, поиск двух самых отдаленных друг от друга может быть выполнен "в среднем" в постоянное время после того, как будет известен ограничивающий круг. В более высоких измерениях число точек в общем положении, необходимых на границе сферы, увеличивается (D + 1 точек для размерности D), и действительно, стоимость вычисления расстояния между одной парой точек возрастает линейно с размерностью.

Подмножество точек, лежащих на ограничивающей окружности или сфере, также находится в линейном времени. В теоретическом наихудшем случае все точки лежат на ограничивающей окружности или сфере, но это, по крайней мере, более строгое, чем просто наличие всех точек на выпуклой оболочке. Если точки на сфере независимо возмущены, скажем, вдоль радиальных линий, то общее положение обеспечивается с вероятностью 1, а приблизительный диаметр может быть найден только из D + 1 точек на пересмотренной охватывающей сфере. Это рандомизированное приближение имеет квадратичную зависимость от размерности, но только линейную сложность в количестве точек.

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

В 2001 году Рамосу удалось показать детерминированный алгоритм O (n log n) для трехмерных множеств, но метод настолько вовлечен что реализация может быть нецелесообразно или медленнее, чем поиск всех пар в грубой силе до очень больших наборов данных.

Для более высоких измерений многие авторы рассмотрели рандомизированный или приблизительные алгоритмы. См. Тезис Петра Индыка (2000) для приближенных методов с только полиномиальной зависимостью от размерности для различных проблем близости.

Ответ 3

Как уже упоминалось в этом ответе, вы ищете "диаметр" множества N точек, хорошо известную проблему в вычислительной геометрии. Существуют два этапа:

Найдите выпуклую оболочку точек. Существуют алгоритмы, которые являются O (N ln N), в худшем случае. На практике QuickHull обычно является быстрым выбором, хотя потенциально O (N ^ 2) наихудший. реализация QHull удобно вызывать из командной строки. Библиотека CGAL предоставляет реализацию С++
Антиподовые пары на выпуклой оболочке являются кандидатами на самые дальние пункты. Можно искать по антиподальным точкам с помощью алгоритма, такого как Вращающиеся суппорты в O (N) времени.

Задача может быть обобщена на проблему "все-самые большие пары": для каждой точки i найдите самую удаленную точку j --- мы теперь ищем N пар точек. Решение снова использует выпуклую оболочку, но теперь вторая часть может быть выполнена с помощью алгоритма поиска матриц.

Ответ 4

Не совсем - общий подход - группировать точки в кластеры, а затем сохранять расстояния между кластерами.

Таким образом, вам не нужно проверять, находится ли какой-нибудь дом в Нью-Йорке от Парижа, если вы уже определили, что Австралия находится дальше.

Ответ 5

Расстояние от A до B совпадает с расстоянием от B до A. Вы можете легко изменить алгоритм таким образом, чтобы исключить половину вычислений. Он все равно будет O(n^2), но будет в два раза быстрее.

То есть вместо вычисления всех недиагональных элементов матрицы расстояния P x P:

P = {A, B, C, D, ...}

  + A + B + C + D + ...
A |   | * | * | * | ...
B | * |   | * | * | ...
C | * | * |   | * | ...
D | * | * | * |   | ...
  |   |   |   |   |

вы можете вычислить либо верхний треугольник:

  + A + B + C + D + ...
A |   | * | * | * | ...
B |   |   | * | * | ...
C |   |   |   | * | ...
D |   |   |   |   | ...
  |   |   |   |   |

или нижний треугольник:

  + A + B + C + D + ...
A |   |   |   |   | ...
B | * |   |   |   | ...
C | * | * |   |   | ...
D | * | * | * |   | ...
  |   |   |   |   |

Ответ 6

См. Джон Фэминелла отличный ответ на этот похожий вопрос. Вы должны получить O (n log n) для среднего случая.

Ответ 7

Я не уверен, что помещать точки в пространственный индекс, и запрос на него приводит к алгоритму O (n log n).

Ответ 8

Если вы часто выполняете этот запрос, но точки не сильно меняются, вы можете выполнить предварительные вычисления, которые могут ускорить процесс.

Каждая точка может хранить самую удаленную точку от нее и перепроверять каждое добавление точки, если новая точка находится дальше.

Когда вы запрашиваете, вы просто проходите все точки и смотрите на свои кешированные точки.

В итоге вы получите O (n) для новой записи точки и O (n) для наиболее удаленного запроса.