Обнаружил для себя, что для некоторых запросов kd-tree долго работает. Как я понял, то в худшем случае может пробегаться все дерево. Wiki подтверждает это.
Есть ли какие-то альтернативы кроме Вороного? Интересны 2d и 3d размерности с Евклидовой метрикой.
Нашел cover tree. Кто-то писал его? Как оно работает?