Faculty       Staff       Students & Alumni       Committees       Contact       Institute Directory
 All Research Groups       PhD Theses       Technical Reports       Institute Research
 Colloquia       Seminars       News       Events       Institute Events
 Overview       Lab Manual       Institute Computing

Research

# Ph.D. Theses

## Extending Neighborhood Problems: Algorithms and Analysis

By Robin Y. Flatland
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.