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

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

Ближайшая соседняя поисковая Анимация NN, ищущего с Деревом KD в 2D

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

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

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