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

Есть ли какие-то альтернативы кроме Вороного? Интересны 2d и 3d размерности с Евклидовой метрикой.

Нашел cover tree. Кто-то писал его? Как оно работает?

Есть список непересекающихся в пространстве кубоидов (прямоугольных параллелепипедов). Каждый кубоид задан координатами минимума и максимума для трех осей (либо координатами его вершин). Значение координат — целое число от 0 до 2^30.

Есть три вида запроса:

1) Добавить новый кубоид

2) Удалить существующий кубоид

3) Вывести номер кубоида, который пересекает заданную точку (x,y,z)