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

Question

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

Например, учитывая набор точек, где каждая строка имеет вид: 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): вычислить расстояние каждой точки до каждой другой точки. Возвратите минимальное расстояние точки для этой точки. Повторите процесс для других точек

Answer 1

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

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

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

Answer 2

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

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