About Me

I am a computer science PhD candidate at the University of Maryland advised by David Mount. I do research on geometric approximation algorithms with broader interests in geometric computing and theoretical computer science. A recurring theme in my research is the approximation of smooth surfaces by efficient discrete representations. My thesis work concerns the approximation of convex polytopes and distance functions for the purposes of nearest-neighbor searching. I also spent some time developing meshing algorithms at Sandia National Labs hosted by Mohamed Ebeida and Scott Mitchell. In recent collaborations, I started exploring geometric deep learning to complement my toolkit with a data-driven perspective.

Selected Projects

Economical Delone Sets for Approximating Convex Bodies
with D. Mount SWAT'18
Abstract Convex bodies are ubiquitous in computational geometry and optimization theory. The high combinatorial complexity of multidimensional convex polytopes has motivated the development of algorithms and data structures for approximate representations. This paper demonstrates an intriguing connection between convex approximation and the classical concept of Delone sets from the theory of metric spaces. It shows that with the help of a classical structure from convexity theory, called a Macbeath region, it is possible to construct an epsilon-approximation of any convex body as the union of O(1/epsilon^{(d-1)/2}) ellipsoids, where the center points of these ellipsoids form a Delone set in the Hilbert metric associated with the convex body. Furthermore, a hierarchy of such approximations yields a data structure that answers epsilon-approximate polytope membership queries in O(\log (1/\epsilon)) time. This matches the best asymptotic results for this problem, by a data structure that both is simpler and arguably more elegant. | PDF
Sampling Conditions for Conforming Voronoi Meshing by the VoroCrust Algorithm
with C. Bajaj, M. Ebeida, A. Mahmoud, S. Mitchell, J. Owens, and A. Rushdi SoCG'18
Abstract We study the problem of decomposing a volume bounded by a smooth surface into a collection of Voronoi cells. Unlike the dual problem of conforming Delaunay meshing, a principled solution to this problem for generic smooth surfaces remained elusive. VoroCrust leverages ideas from & alpha;-shapes and the power crust algorithm to produce unweighted Voronoi cells conforming to the surface, yielding the first provably-correct algorithm for this problem. Given an & epsilon;-sample on the bounding surface, with a weak & sigma;-sparsity condition, we work with the balls of radius & delta; times the local feature size centered at each sample. The corners of this union of balls are the Voronoi sites, on both sides of the surface. The facets common to cells on opposite sides reconstruct the surface. For appropriate values of & epsilon;, & sigma; and & delta;, we prove that the surface reconstruction is isotopic to the bounding surface. With the surface protected, the enclosed volume can be further decomposed into an isotopic volume mesh of fat Voronoi cells by generating a bounded number of sites in its interior. Compared to state-of-the-art methods based on clipping, VoroCrust cells are full Voronoi cells, with convexity and fatness guarantees. Compared to the power crust algorithm, VoroCrust cells are not filtered, are unweighted, and offer greater flexibility in meshing the enclosed volume by either structured grids or random samples. | arXiv
Approximate Nearest Neighbor Searching with Non-Euclidean and Weighted Distances
with S. Arya, G. da Fonseca, and D. Mount SODA'19
Abstract We present a new approach to epsilon-approximate nearest-neighbor queries in fixed dimension under a variety of non-Euclidean distances. We consider two families of distance functions: (a) convex scaling distance functions including the Mahalanobis distance, the Minkowski metric and multiplicative weights, and (b) Bregman divergences including the Kullback-Leibler divergence and the Itakura-Saito distance.

As the fastest known data structures rely on the lifting transformation, their application is limited to the Euclidean metric, and alternative approaches for other distance functions are much less efficient. We circumvent the reliance on the lifting transformation by a careful application of convexification, which appears to be relatively new to computational geometry.

We are given n points in R^d, each a site possibly defining its own distance function. Under mild assumptions on the growth rates of these functions, the proposed data structures answer queries in logarithmic time using O(n log(1/epsilon) epsilon^(-d/2)) space, which nearly matches the best known results for the Euclidean metric.
| Slides