PhD Proposal: Geometric Data Structures for Approximating Shapes and Functions

Geometric spaces provide convenient data representations relevant to many application domains. Due to the intractability of exact solutions to numerous fundamental problems on such data sets, it is necessary to study efficient approximation schemes. I propose to develop new algorithms and data structures for various problems in geometric approximation.The starting point of my research is to revisit recent approaches to the approximation of convex polytopes and approximate nearest neighbor searching. These approaches exploit a classical construct from the theory of convexity, called Macbeath regions. By elaborating on the similarities between Macbeath regions and metric balls in a suitable metric intrinsic to the data, my recent work has developed a simplified design principle for such data structures. In doing so, a number of extraneous technical complications was eliminated, paving the way to applying this new principle in more general settings.Building upon these preliminary results, I intend to study nearest neighbor searching under more general distance metrics, beyond the standard Euclidean distance, as well as the approximation of more general functions, beyond the distance function to a discrete set of points. At the same time, I seek a deeper understanding of the constructs involved and their potential generalizations and applications to other classes of problems.

Examining Committee:

Chair: Dr. David Mount Dept. rep: Dr. Ramani Duraiswami Members: Dr. Samir Khuller