|
||||||||||||||||
|
Ph.D. ThesesExtending Neighborhood Problems: Algorithms and Analysis
By Robin Y. Flatland
Extending neighborhood problems, a new class of problems in computational geometry, generalizes the traditional range queries and nearest neighbors problems. In the traditional problems, the objective is to preprocess a set of points so that points inside a query region or nearest a query point can be quickly reported. In extending neighborhood problems, however, the problem is to efficiently report the new points incorporated by a query as it incrementally increases in size on-line. As an example, when neighborhoods are defined in terms of query regions, the initial neighborhood is a small region of space, and each extended neighborhood is a larger region encompassing the previous one. The problem is to efficiently find just the new points included by the query as it increases in size. Applications of these problems include surface reconstruction techniques in computer vision that grow out surfaces in range data, nearest neighbor classification techniques, and information retrieval systems. This thesis examines algorithmic issues of several different instances of extending neighborhood problems. Two fundamental problem instances extend axis-aligned rectangular regions and nearest neighbors using the $L_\infty$ metric. Although these problems may be trivially solved with repeated applications of traditional range query or nearest neighbor algorithms, asymptotically more efficient solutions are presented that take advantage of the fact that entire sequences of neighborhoods are processed. The extending $L_\infty$ nearest neighbors algorithm also provides a new solution to the traditional $L_\infty$ k nearest neighbors problem, improving upon previous results. With some modifications, these algorithms generalize to extending polytope range queries and extending nearest neighbors using polytope distance functions. The final problem instance extends sequences of nested rectangular query regions where all queries in a sequence have the same orientation, but the orientation of each sequence may differ. A linear space algorithm is presented that performs partially ordered searches of a box-decomposition subdivision. A query sensitive analysis and empirical results show the algorithm is effective for ``targeted'' queries, queries that target space containing a high density of data relative to the space immediately surrounding the query. Such queries are typical of those made by region growing surface reconstruction techniques, the primary application considered here.
|
||||||||||||||||
Research
