Please use this identifier to cite or link to this item:

New results in nearest neighbor and range searching

Authors Xia, Jian
Issue Date 2010
Summary In this thesis, we tackle challenging open questions in the area of nearest neighbor and range searching. Nearest neighbor and range searching are among the most fundamental problems in computational geometry, with numerous applications in areas such as pattern recognition, machine learning, and information retrieval. In these problems, we have to preprocess the given point set in some space into a data structure according to the query type, so that queries can be answered efficiently. In our research, we have obtained the following three results. Our first two results concern approximate nearest neighbor searching in the context of metric spaces. We show that the concept of approximate Voronoi diagram (AVD), which is known to provide the most efficient solution in Euclidean spaces, can be generalized to doubling spaces as well as to hyperbolic spaces. This enables us to achieve much faster query times than previously possible, and also achieve space-time tradeoffs for the first time. Our third result is concerned with the complexity of halfspace range searching. We consider this problem in a weighted setting, where each point is associated with a weight from a commutative semigroup, and the output of the query is the semigroup sum of the weights of the points lying within the halfspace. We establish two new lower bounds for this problem in the semigroup arithmetic model. Neglecting logarithmic factors, our result for integral semigroups matches the best known upper bound due to Matoušek. Our result for general semigroups improves upon the best known lower bound due to Brönnimann, Chazelle, and Pach. Moreover, it also resolves the computational complexity of halfspace range searching over idempotent semigroups in the important special case of uniformly distributed point sets.
Note Thesis (Ph.D.)--Hong Kong University of Science and Technology, 2010
Language English
Format Thesis
Access View full-text via DOI
Files in this item:
File Description Size Format
th_redirect.html 341 B HTML
Copyrighted to the author. Reproduction is prohibited without the author’s prior written consent.