ближайший сосед - дерево k-d - доказательство википедии

НаВикипедия для деревьев K-Dпредставлен алгоритм для поиска ближайшего соседа по дереву k-d. Что я не понимаю, так это объяснение шага 3.2. Откуда вы знаете, что не существует более близкой точки только потому, что разница между координатой разделения точки поиска и текущего узла больше, чем разница между координатой разделения точки поиска и текущей наилучшей?

Поиск ближайшего соседа Анимация поиска NN с KD-деревом в 2D

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

Начиная с корневого узла, алгоритм рекурсивно перемещается вниз по дереву так же, как если бы точка поиска была вставлена (т. Е. Идет вправо или влево в зависимости от того, больше или меньше точка текущего узла в разделить измерение).Как только алгоритм достигает конечного узла, он сохраняет точку этого узла как «текущий лучший»Алгоритм раскручивает рекурсию дерева, выполняя следующие шаги на каждом узле: 1. Если текущий узел ближе, чем текущий лучший, то он становится текущим лучшим. 2. Алгоритм проверяет, могут ли быть какие-либо точки на другой стороне плоскости разбиения, которые находятся ближе к точке поиска, чем текущая наилучшая. Концептуально это делается путем пересечения расщепляющейся гиперплоскости с гиперсферой вокруг точки поиска, радиус которой равен текущему ближайшему расстоянию. Поскольку все гиперплоскости выровнены по оси, это реализуется как простое сравнение, чтобы увидеть, меньше ли разница между координатой расщепления точки поиска и текущего узла, чем расстояние (общие координаты) от точки поиска до текущего лучшего. 1. Если гиперсфера пересекает плоскость, на другой стороне плоскости могут быть более близкие точки, поэтому алгоритм должен перемещаться вниз по другой ветви дерева от текущего узла в поисках более близких точек, следуя тому же рекурсивному процессу, что и весь поиск. 2. Если гиперсфера не пересекает плоскость расщепления, то алгоритм продолжает идти вверх по дереву, и вся ветвь на другой стороне этого узла удаляется.Когда алгоритм завершает этот процесс для корневого узла, поиск завершается.

Обычно алгоритм использует квадрат расстояния для сравнения, чтобы избежать вычисления квадратных корней. Кроме того, он может сохранить вычисления, удерживая квадратное текущее наилучшее расстояние в переменной для сравнения.