Какой самый быстрый способ обнаружить две точки в 2D-пространстве с наибольшим расстоянием между ними?

Question

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

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

Так что я ищу более быстрое решение.

Answer 1

Как насчет:

1 Определить выпуклую оболочку из набора точек.
2 Найдите наибольшее расстояние между точками на корпусе.

Это должно позволить вам игнорировать всеточки на корпусе при проверке расстояния.

Answer 2

Для уточнения ответа Россома:

1. Найдите выпуклую оболочку точек, которые можно найти за O (n log n), с помощью алгоритма, подобного сканированию Грэхэма или O (n log h)время с другими алгоритмами, которые, как я полагаю, сложнее реализовать
2. Начните с точки, скажем, A, и переберите другие точки, чтобы найти самую дальнюю от нее, скажем, B.
3. Advance Aк следующему пункту и продвиньтесь B, пока это не будет самым дальней от A снова.Если это расстояние больше, чем в части 2, сохраните его как наибольшее.Повторяйте, пока не пройдете все точки A в наборе

. Части 2 и 3 занимают амортизированное время O (n), и, следовательно, общий алгоритм занимает O (n log n) или O (n log h).) время, зависящее от того, сколько времени вы можете потратить на реализацию выпуклого корпуса.

Это здорово, и все, но если у вас всего несколько тысяч очков (как вы сказали), O (n ^ 2) должноработать нормально (если вы не выполняете это много раз).