A bisector tree allows to do fast but exact nearest neighbor searches in
any space provided that you have a metric (function) to measure the
distance between any two points in that space.
It also allows proximity queries, as in “all points within distance d
from my query point”.
Cf. this article for details: “A Data Structure and an Algorithm for the
Nearest Point Problem”; Iraj Kalaranti and Gerard McDonald.
The code is here:
It might interest users of vantage point trees (minivpt, and vpt in
opam), kd-trees and such.
I think bst should be faster than vpt in most use cases.
It should appear in opam shortly.