log in  |  register  |  feedback?  |  help  |  web accessibility
PhD Proposal: Efficient Algorithms for processing Evolving Geometric data
Aditya Acharya
Wednesday, April 20, 2022, 10:30 am-12:30 pm Calendar
  • You are subscribed to this talk through .
  • You are watching this talk through .
  • You are subscribed to this talk. (unsubscribe, watch)
  • You are watching this talk. (unwatch, subscribe)
  • You are not subscribed to this talk. (watch, subscribe)

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


Adi is a PhD student working with Prof. Dave Mount. He's especially interested in the theoretical, and fundamental aspects of Computational Geometry.

Of late he's working on Geometric problems on uncertain and evolving data-sets. In the past he has dabbled in closely related areas of combinatorial geometry, and computational topology.

This talk is organized by Tom Hurst