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

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

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