Found for myself that for some queries kd-tree works for a long time. As I understand it, in the worst case we will traverse all nodes in the tree. The Wiki confirms this.
Are there any alternatives besides Voronoi? Interesting are 2d and 3d dimensions with Euclidean metric.
Found cover tree. Did someone write it? How does it work?