Нахождение трех точек, ближайших к каждой точке на 2D-плоскости

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

Например, задан набор точек, где каждая линия имеет вид: ID x-координата y-координата

1 0.0 0.0  
2 10.1 -10.1   
3 -12.2 12.2   
4 38.3 38.3   
5 79.99 179.99

Ваша программа должна вывести:

1 2,3,4   
2 1,3,4   
3 1,2,4   
4 1,2,3   
5 4,3,1

Это вопрос интервью, который я нашел на онлайн-форуме. Я могу придумать решение O(n*n): вычислить расстояние от каждой точки до любой другой точки. Возвращает точки минимального расстояния для этой точки. Повторите процесс для других точек


algorithm computational-geometry
person TimeToCodeTheRoad    schedule 16.01.2012    source источник
comment
Какой у Вас вопрос? Вы ищете решение, которое быстрее, чем O(N*N)?   -  person Sergey Kalinichenko    schedule 16.01.2012
comment
Это довольно плохой вопрос для собеседования, особенно если цель состоит в том, чтобы придумать настоящий код. Получить работающее решение (сложность которого может быть приемлема в некоторых контекстах) тривиально, как вы примерно сделали, но его довольно сложно улучшить. Особенно, если вы понятия не имеете о структурах, используемых в вычислительной геометрии. В любом случае, поиск ближайшего соседа (u)r в Google должен дать вам много указаний. Хорошее начало — эта статья в Википедии   -  person Alexandre C.    schedule 16.01.2012
comment
@dasblinkenlight, нет, он ищет алгоритм для работы за O (n ^ n).   -  person Saeed Amiri    schedule 16.01.2012
comment
На самом деле, кажется, есть O(n log n) решение в этой статье.   -  person Alexandre C.    schedule 16.01.2012
comment
возможный дубликат Все k ближайших соседей в 2D, C++   -  person Alexandre C.    schedule 16.01.2012
comment
Вашему интервьюеру нравятся очки? ваш предыдущий вопрос был об этом, это домашняя работа или ваши экзаменационные проблемы?   -  person Saeed Amiri    schedule 16.01.2012
comment
@dasblinkenlight: я ищу решение быстрее, чем O (n * n)   -  person TimeToCodeTheRoad    schedule 16.01.2012

Ответы (2)


arrow_upward
4
arrow_downward

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

В качестве альтернативы, если вы знаете, что точки в основном распределяются случайным образом, вы можете рассмотреть возможность разделения пространства на набор сегментов некоторого фиксированного размера. Чтобы найти ближайших соседей к точке, вы можете просмотреть все точки в одном и том же сегменте, затем все точки в соседних сегментах и ​​т. д. Это должно быть близко к O(n/b) времени на точку, если точки хорошо распределено и есть b ведер.

Надеюсь это поможет!

person templatetypedef    schedule 16.01.2012

arrow_upward
3
arrow_downward

Они ищут, слышали ли вы когда-нибудь о триангуляции Делоне, которая затем приводит к O (n log n).

Изменить. Это не так просто, как я предполагал, согласно поправке в комментариях. Можно можно использовать триангуляцию Делоне, чтобы найти трех ближайших соседей за время O(n log n), но это требует некоторой работы, как объясняется в статье Дикерсона, Драйсдейла и Сака «Простые алгоритмы для перечисления межточечных расстояний и Поиск k ближайших соседей."

person Joseph O'Rourke    schedule 16.01.2012
comment
Триангуляция Делоне не гарантирует получение ближайших 3 точек. Ближайший 1 определенно. Ближайшие 2 может быть, я не уверен. Ближайшие 3, НЕТ. - person ElKamina; 17.01.2012
comment
@ElKamina: я исправляюсь! Я обновил свой вводящий в заблуждение ответ, чтобы отразить ваше исправление. - person Joseph O'Rourke; 17.01.2012