Analysis of range search for random k-d trees |
| |
Authors: | Philippe Chanzy Luc Devroye Carlos Zamora-Cura |
| |
Affiliation: | (1) School of Computer Science, McGill University, Montreal, Canada H3A 2K6 (e-mail: {luc,czamora}@cs.mcgill.ca), CA |
| |
Abstract: | We analyze the expected time complexity of range searching with k-d trees in all dimensions when the data points are uniformly
distributed in the unit hypercube. The partial match results of Flajolet and Puech are reproved using elementary probabilistic
methods. In addition, we give asymptotic expected time analysis for orthogonal and convex range search, as well as nearest
neighbor search. We disprove a conjecture by Bentley that nearest neighbor search for a given random point in the k-d tree
can be done in O(1) expected time.
Received: 27 July 1999 / 2 June 2000 |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|