HKUST Library Institutional Repository Banner

HKUST Institutional Repository >
Computer Science and Engineering >
CSE Doctoral Theses >

Please use this identifier to cite or link to this item:
Title: New results in nearest neighbor and range searching
Authors: Xia, Jian
Issue Date: 2010
Abstract: 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.
Description: Thesis (Ph.D.)--Hong Kong University of Science and Technology, 2010
vii, 84 p. : ill. ; 30 cm
HKUST Call Number: Thesis CSED 2010 XiaJ
Appears in Collections:CSE Doctoral Theses

Files in This Item:

File Description SizeFormat

All items in this Repository are protected by copyright, with all rights reserved.