Будут 2 дерева (буду писать как координата, номер точки). По х: 2,3 1,1

5,2
По у:
2,3
1,2 5,1

Теперь пытаюсь искать ближайшую по х точку по дереву (о, а получается узлы дерева мне тоже надо проверять что ли?)

От (0,0) до третьей точки расстояние 2√2, пока она ближайшая (вообще тут должно было сработать условие d<3 и точка уже в этом кластере, можно дальше не считать. Но попробую чтоб лучше покрутить алгоритм в голове)
Идём в лист. В левый получается. Считаем расстояние до точки 1. Это √26. Пока ближайшей осталась третья. Дерево по х кончилось, точку 2 мы не проверяли, экономия

Теперь опускаемся по дереву у:
Снача с третьей точкой сравниваем, ну это уже было. Ближайшая не меняется
Дальше опускаюсь по дереву, с точкой 2 сравниваю: расстояние √26, лидер всё ещё точка 3

Точка (0,0) в кластере, добавляю её в деревья:
По х:
2,3
1,1 5,2
0,0
По у:
2,3
1,2 5,1
0,0

Кажется я переизобрёл кд-дерево 😔

То есть ты собираешься проверять все вершины на пути к ближайшему? А как выбирать в какую ветку спускать: в левую или в правую? Если не посещать обе, то вполне можно пропустить ближайшую

Или ставка именно на то, что по отдельности деревья сломать можно, но вместе они точно найдут правильный ответ? Мой пример был для того чтобы показать, что ближайшая точка не обязательно является ближайшей по x или ближайшей по y

Да, я это не предусмотрел, но похоже надо узлы при спуске тоже проверять

Ну я как раз и хотел чтобы оценили будет такая идея работать или нет

Наверное я не прав и спуск по дереву не гарантирует что по пути будет ближайшая из возможных точек

Кстати, а насколько большое d? Интересует даже не d, а плотность точек. Насколько много точек может быть в одном кубике d x d x d? Кажется, что это можно назвать каким-нибудь k и использовать в асимптотике

вообще не понятно сколько брать чтобы можно было кузов как отдельный кластер выделить. пока неплохо работает d^2=30_000 я сравниваю квадраты расстояний

ну ориентировочно в d*d*d может быть до 961 точки

Ещё есть идея прорядить точки раза в 4 и даже за O(n^2) искать слегка увеличив d

А-н-нет, потом же всё равно нужно будет искать куда относятся остальные точки

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