Как найти две самые дальние точки?

Question

Это вопрос, который мне задавали на собеседовании некоторое время назад. И я до сих пор не могу найти разумного ответа.

Вопрос:

Вам дан набор точек (x, y). Найдите 2 самые отдаленные точки. Отдаленные друг от друга.

Например, для точек: (0,0), (1,1), (-8, 5) - наиболее удаленными являются: (1,1) и (-8,5), потому что расстояние между ними больше от (0,0) - (1,1) и (0,0) - (- 8,5).

Очевидный подход - вычислить все расстояния между всеми точками и найти максимум. Проблема в том, что это O (n ^ 2), что делает его слишком дорогим для больших наборов данных.

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

Пытался искать в Интернете, но не нашел никакого разумного ответа - хотя это может быть просто отсутствие у меня навыков поиска.

Answer 1

РЕДАКТИРОВАТЬ: Один из способов найти выпуклый корпус http://en.wikipedia.org/wiki/Convex_hull из набора точек, а затем два отдаленные точки являются вершинами этого.

Возможно, ответили здесь: Алгоритм нахождения двух точек, наиболее удаленных друг от друга

Также:

• http://mukeshiiitm.wordpress.com/2008/05/27/find-the-farthest-pair-of-points/

Answer 2

Алгоритмы граничных точек имеются в большом количестве (ищите алгоритмы выпуклой оболочки). Оттуда потребуется O (N) время, чтобы найти наиболее удаленные противоположные точки.

Из комментария автора: сначала найдите любую пару противоположных точек на корпусе, а затем обойдите его полукруглым шагом. В зависимости от углов между краями вам придется продвигаться либо на одного ходунка, либо на другого, но для обхода корпуса всегда требуется O (N).

Answer 3

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

Answer 4

Этот вопрос вводится при введении в алгоритм. В нем упоминается 1) Рассчитать выпуклую оболочку O (NlgN). 2) Если есть M vectex на выпуклой оболочке. Тогда нам нужно O (M), чтобы найти самую дальнюю пару.

Я считаю это полезными ссылками. Включает анализ деталей алгоритма и программы. http://www.seas.gwu.edu/~simhaweb/alg/lectures/module1/module1.html

Желаю, чтобы это было полезно.

Answer 5

Вы ищете алгоритм для вычисления диаметра набора точек, Диаметр (S) . Можно показать, что это совпадает с диаметром выпуклой оболочки S, Diam (S) = Diam (CH (S)) . Поэтому сначала вычислите выпуклую оболочку множества.

Теперь вы должны найти все антиподальные точки на выпуклой оболочке и выбрать пару с максимальным расстоянием. На выпуклом многоугольнике есть O (n) антиподальных точек. Таким образом, это дает алгоритм O (n lg n) для нахождения самых дальних точек.

Этот метод известен как Вращающиеся суппорты . Это то, что Марсело Кантос описывает в своем ответе.

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

Answer 6

Стохастический алгоритм для поиска наиболее удаленной пары будет

• Выберите случайную точку
• Получите точку, наиболее удаленную от нее
• Повторите несколько раз
• Удалить все посещенные точки
• Выберите другую случайную точку и повторите несколько раз.

Вы находитесь в O (n) до тех пор, пока вы предопределяете «несколько раз», но не гарантированно найдете самую дальнюю пару. Но в зависимости от вашего набора очков результат должен быть довольно хорошим. =)

Answer 7

посмотрите на прямоугольные треугольники A- (x1, y1), B- (x2, y2) и расстояние b / w A и B равно = sqrt [(| x1 | + | x2 |) ^ 2 + (| y1 | + | y2 |) ^ 2]

Answer 8

При заданном наборе точек {(x1, y1), (x2, y2) ... (xn, yn)} найдите 2 наиболее удаленные точки.

Мой подход:

1). Вам нужна контрольная точка (xa, ya), и она будет:
xa = (x1 + x2 + ... + xn) / n
ya = (y1 + y2 + ... + yn) / n

2). Вычислить все расстояния от точки (xa, ya) до (x1, y1), (x2, y2), ... (xn, yn)
Первая «самая удаленная точка» (xb, yb) - это точка с максимальным расстоянием.

3). Вычислить все расстояния от точки (xb, yb) до (x1, y1), (x2, y2), ... (xn, yn)
Другая «самая удаленная точка» (xc, yc) - это точка с максимальным расстоянием.

Итак, вы получили свои самые отдаленные точки (xb, yb) (xc, yc) в O (n)

Например, для точек: (0,0), (1,1), (-8, 5)

1). Контрольная точка (xa, ya) = (-2,333, 2)

2). Рассчитать расстояния:
от (-2,333, 2) до (0,0): 3,073
от (-2,333, 2) до (1,1): 3,480
от (-2,333,2) до (-8,5): 6,411
Итак, первая самая дальняя точка (-8, 5)

3). Рассчитать расстояния:
от (-8, 5) до (0,0): 9,434
от (-8, 5) до (1,1): 9,849
от (-8, 5) до (-8, 5): 0
Таким образом, другой наиболее удаленный пункт (1, 1)

Answer 9

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

1. Найдите точки с максимальными и минимальными значениями их координат x, y и z (всего 6 точек). Это должны быть самые «отдаленные» из всех граничных точек.
2. Вычислить все расстояния (30 уникальных расстояний)
3. Найти максимальное расстояние
4. Две точки, которые соответствуют этому максимальному расстоянию, являются теми, которые вы ищете.

Answer 10

Отправной точкой может быть рассмотрение ближайших проблем, которые были рассмотрены. В Википедии перечислены некоторые параметры:

http://en.wikipedia.org/wiki/Closest_point_query