ближайший сосед 2 измерения

Question

При заданном множестве S точек в двумерном пространстве, вы получите алгоритм, который вычисляет ближайший сосед (евклидово) для каждой точки множества. Я думаю, что это называется ближайшим рядом граф, не так ли? Любой существующий эффективный алгоритм (N log N), где N = len (S)?

Answer 1

kd-tree - довольно стандартный алгоритм поиска ближайшего соседа (даже в 2-х местах, не позволяйте первой иллюстрации бросать вас).