Как найти два большинство удаленных точек?
Это - вопрос, что меня спросили относительно собеседования некоторое время назад. И я все еще не могу выяснить разумный ответ.
Вопрос:
Вам дают набор точек (x, y). Найдите 2 большинство удаленных точек. Удаленный друг от друга.
Например, для точек: (0,0), (1,1), (-8, 5) - самые удаленные: (1,1) и (-8,5), потому что расстояние между ними больше и от (0,0) - (1,1) и от (0,0) - (-8,5).
Очевидный подход должен вычислить все расстояния между всеми точками и найти максимум. Проблема состоит в том, что это - O (n^2), который делает это непомерно дорогим для больших наборов данных.
Существует подход с первыми точками отслеживания, которые находятся на границе и затем вычислении расстояний для них, по предпосылке, что будет меньше точек на границе, чем "внутри", но это все еще дорого, и перестанет работать в худшем варианте развития событий.
Попробованный для поиска сети, но не нашел разумного ответа - хотя это могло бы быть просто моим отсутствием поисковых навыков.
5 ответов
РЕДАКТИРОВАТЬ: Один из способов - найти выпуклый корпус http://en.wikipedia.org/wiki/Convex_hull множества точек, а затем две удаленные точки являются вершинами этого набора.
Возможный ответ здесь: Алгоритм поиска двух точек, наиболее удаленных друг от друга
Также:
Алгоритмы граничных точек изобилуют (ищите алгоритмы выпуклой оболочки). Оттуда потребуется O (N) времени, чтобы найти самые далекие противоположные точки.
Из комментария автора: сначала найдите любую пару противоположных точек на корпусе, а затем обойдите ее полусамым шагом. В зависимости от углов между краями вам придется продвигать либо одного шагохода, либо другого, но для обхода корпуса всегда потребуется O (N).
Несколько мыслей:
Вы можете смотреть только на точки, которые определяют выпуклую оболочку вашего набора точек, чтобы уменьшить число, .. ... но все равно выглядит немного «неоптимально».
В противном случае может быть подход рекурсивного квадро / октодерева для быстрого ограничения некоторых расстояний между наборами точек и удаления больших частей ваших данных.
Стохастический алгоритм для поиска наиболее удаленной пары будет выглядеть так:
- Выбрать случайную точку
- Получить точку, наиболее удаленную от нее
- Повторить несколько раз
- Удалить все посещенные точки
- Выбрать другую случайный момент и повторите несколько раз.
Вы находитесь в O (n), пока вы заранее определите «несколько раз», но нет гарантии, что вы действительно найдете самую дальнюю пару. Но в зависимости от вашего набора очков результат должен быть довольно хорошим. =)
Отправной точкой может стать рассмотрение проблем с замыканием, которые были рассмотрены. Википедия перечисляет некоторые варианты: