Поиск ближайшего узла сетки к заданной точке

[Olegzzz]

Задача: есть некая сетка узлов (возможно, не регулярная). Необходимо найти номер ближайшего узла к заданной произвольной точке. Просто перебор и подсчет всех расстояний до точки - долго. Какие есть идеи, мысли по этому поводу? Есть ли стандартное название у этой задачи?

Добавлено спустя 14 минут 13 секунд:

Есть идея создать индексы координат узлов по каждому измерению отсортированные по возрастанию (или убыванию - неважно). Тогда по каждому измерению можно найти ближайшую координату (с помощью бинарного поиска). Но что дальше?

[PAV]

Можно попробовать разбить рабочую область пространства на куски (ячейки) и хранить список узлов в каждой ячейке. Далее по заданной точке перебираем ячейки в порядке возрастания расстояния до данной точки. По каждой ячейке быстро определяется, есть ли в ней хоть один узел, если да - то узлы перебираются. Когда хоть один узел найден, то многие ячейки уже перебирать уже вообще не надо будет.

Вообще же это называется диаграмма Вороного, см. например здесь или в поисковике. Объект известный.

Добавлено спустя 2 минуты 36 секунд:

Есть статья в Википедии, правда, там почти ничего нет.

[worm2]

Вроде R-деревья используются для решения этой задачи.

Добавлено спустя 16 минут 53 секунды:

А стандартное её название --- Задача поиска ближайшего соседа.

[Zai]

Попробуйте библиотеки программ векторных операций. Разности координат точки и всех узлов будет тремя векторами. Их можно ссумировать по абсолютной величине, а затем в векторной операции найдти номер минимума (это тоже векторная операция).