Поиск двумерных точек с короткими промежуточными прыжками

Question

У меня есть список allNodes около 60 000 узлов, соответствующих 2D-точкам. Я построение списка смежности как

for(i in allNodes) 
    for(j in allNodes) 
    if(distance(i, j) <= 10) addEdge between i and j 

, а затем выполняя поиск в глубину из набора sourceNodes найти множество узлов достижимо из sourceNodes. Как я могу сделать это быстрее, чем квадратично? Я использую C++.

Answer 1

Метод биннинга, предложенный ответом Дэвида Эйзенстата, работает, если вы ожидаете однородности распределенных точек, что не является свойством, которое вы указали о своих данных. Кроме того, как отмечено, Delaunay triangulation по-прежнему требует локального поиска на индуцированном графике, чтобы обеспечить обнаружение всех узлов на указанном расстоянии.

Один из способов получения гарантированного результата - с kd-tree. Вы можете построить его в O (2n log n) времени (или быстрее, если вам не все равно о гарантиях и используйте рандомизацию) и используйте его для выполнения поиска диапазона с общим временем O (2n√n).

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

Answer 2

Простой подход состоит в том, чтобы разделить плоскость на d-d-d, где d> 10 бункеров, и поместить каждую точку в бункер, индексированный полом (x/d), пол (y/d). Затем, вместо того, перебирает все пары точек,

for bin1 in bins: 
    for i in bin1: 
     for bin2 in bins neighboring bin in nine directions (including bin): 
     for j in bin2: 
      if(distance(i, j) <= 10) addEdge between i and j 

Это будет делать вещи быстрее, если точки хорошо разнесены, но в худшем случае еще квадратичная.

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