[4] Uhlmann called the data structure a metric tree, the name VP-tree was proposed by Yianilos.
Vantage-point trees have been generalized to non-metric spaces using Bregman divergence by Nielsen et al.[5] This iterative partitioning process is similar to that of a k-d tree, but uses circular (or spherical, hyperspherical, etc.)
In two-dimensional Euclidean space, this can be visualized as a series of circles segregating the data.
[3] The time cost to search a vantage-point tree to find a single nearest neighbor is O(log n).
There are log n levels, each involving k distance calculations, where k is the number of vantage points (elements) at that position in the tree.
The time cost to search a vantage-point tree for a range, which may be the most important attribute, can vary greatly depending on the specifics of the algorithm used and parameters.
Brin's paper[3] gives the result of experiments with several vantage point algorithms with various parameters to investigate the cost, measured in number of distance calculations.