On the Boundedness of Reverse Nearest Neighbors in Arbitrary Dimensions
Seal, Sudip (2004) On the Boundedness of Reverse Nearest Neighbors in Arbitrary Dimensions. Publisher UNSPECIFIED.
This is the latest version of this eprint.
Full text available as:
Run time analysis of algorithms involving reverse nearest neighbor (RNN) queries, particularly in higher dimensions, often become impossible for lack of hard upper bounds on the maximum size of the reverse nearest neighbor set. In this paper, we present a formulation of the RNN problem which enables calculation of such bounds in the static monochromatic case under the L2-norm in any dimension. We also show that there exists a lower bound on the maximum size of the RNN set and how the gap between the above bounds can be reduced. The results in lower dimensions are remarkably accurate while those in higher dimensions are very promising.
Available Versions of this Item
Archive Staff Only: edit this record