Как найти два самых отдаленных пункта?

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

Вопрос:

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

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

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

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

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

Ответ 1

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

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

Также:

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

Ответ 2

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

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

Ответ 3

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

Ответ 4

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

Я нахожу полезные ссылки. Он включает в себя анализ деталей алгоритма и программы. http://www.seas.gwu.edu/~simhaweb/alg/lectures/module1/module1.html

Пожелайте, чтобы это было полезно.

Ответ 5

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

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

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

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

Ответ 6

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

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

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

Ответ 7

Несколько мыслей:

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

В противном случае может быть рекурсивный подход quad/oct-tree для быстрого привязки некоторых расстояний между множествами точек и устранения больших частей ваших данных.

Ответ 8

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

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

Ответ 9

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

Найдите точки с максимальными и минимальными значениями их координат x, y и z (всего 6 баллов). Они должны быть наиболее "remote" всех граничных точек.
Вычислить все расстояния (30 уникальных расстояний)
Найти максимальное расстояние
Две точки, соответствующие этому максимальному расстоянию, - это те, которые вы ищете.

Ответ 10

Учитывая множество точек {(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)

Ответ 11

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