PhD Proposal: Efficient Algorithms for processing Evolving Geometric data

We consider the problem of maintaining a data structure for a large set of points, which are evolving over the course of time. In this framework, an agent called the evolver, continuously introduces small local changes to the structure behind the scenes. We aim to design algorithms, that judiciously probe the structure to detect local changes, and maintain a view of the structure as close as possible to the true underlying one. This framework captures the tradeoff between the complexity of maintaining an up-to-date view of the structure and the quality of results computed with the available view.

As a first problem in this framework, we design an algorithm to maintain a set of labels assigned to the vertices of a tree, when the locations of these labels keep changing over time. The algorithm can only track these changes by explicitly probing individual nodes of the tree, with the help of a local oracle. Our results allow for both randomized and adversarial evolution of the data, subject to allowing different speedup factors between the algorithm and the evolver. We show that in the limit, our algorithm maintains labels to within an average distance of O(1) of their actual locations. We also present nearly matching lower bounds.

Next, we extend the previous approach to the case where an evolver exchanges the labels of nearby points in the Euclidean space. With the help of a natural oracle, we show how to maintain the labels over a hypothesized structure. We calculate an appropriate constant speed up factor for the algorithm, which is sufficient in maintaining an optimal distance between the true structure, and the hypothesized one.

We next present ideas on how to apply our techniques in motion planning and tracking, over massive graphs using a competitive routing algorithm. We present a randomized algorithm that in expectation maintains an optimal hypothesized structure, subject to allowing a constant speedup factor.

We conclude by presenting one of our works in progress: the problem of maintaining a ubiquitous geometric structure called the quad tree, under the evolving data framework.

Examining Committee:

Chair: Dr. David Mount

Department Representative: Dr. John Yiannis Aloimonos
Dr. William Gasarch