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.

News

old news
  • 10/26/2018: presented work on street network analysis in the Fall Workshop on Computational Geometry FWCG'18 at Queens College, CUNY [slides].
  • 09/27/2018: work on approximate nearest-neighbor searching has been accepted in SODA'19.
  • 06/18/2018: presented work on approximating convex polytopes in SWAT'18 at Malmö University, Sweden [slides].
  • 06/14/2018: presented work on Voronoi meshing in SoCG'18 at the Eötvös University of Budapest, Hungary [slides].
  • 06/12/2018: presented work on approximating convex polytopes in the Young Researchers Forum of SoCG'18.
  • 06/07/2018: video of our Voronoi meshing paper is now available on YouTube.
  • 05/14/2018: attended the Topological and Geometric Data Analisis (TGDA) at Ohio State University TRIPODS Center Summer School + Workshop.
  • 04/26/2018: passed my preliminary examinations.
  • 03/08/2018: work on approximating convex polytopes has been accepted in SWAT'18.
  • 02/24/2018: volunteered as a judge for the department’s Annual High School Programming Contest.
  • 02/15/2018: presented work on Voronoi meshing in the Applied Mathematics Seminar @ MSU.
  • 02/14/2018: work on Voronoi meshing has been accepted in SoCG'18.
  • 11/04/2017: volunteered as a mentor in the all-women hackathon TECHNICA.
  • 11/03/2017: presented work on Voronoi meshing in the Fall Workshop on Computational Geometry FWCG'17 at Stony Brook University.
  • 10/06/2017: spoke about new developments in proximity queries at the Capital Area Theory Seminar (CATS) [slides].
  • 07/04/2017: attended SoCG'17 at Queensland University in Brisbane.
  • 06/19/2017: work on mesh improvement has been accepted in SGP'17.
  • 06/09/2017: work on conforming Voronoi meshing has been accepted in CCCG'17.
  • 03/03/2017: spoke about Semidefinite Programming and approximating Max-Cut at the Capital Area Theory Seminar (CATS) [slides].
  • 02/18/2017: volunteered as a judge for the department’s Annual High School Programming Contest.
  • 01/18/2017: work on surveillance by mobile cameras has been accepted in IPSN'17.
  • 10/27/2016: Fall Workshop on Computational Geometry (FWCG'16) at CUNY.
  • 09/20/2016: presented work on pursuit-evasion games in the Computational Intelligence and Games Conference CIG'16 in Greece.
  • 06/16/2016: presented work on homology localization in the Young Researchers Forum of SoCG'16 at Tufts University.
  • 06/14/2016: work on visibility-based pursuit-evasion has been accepted in CIG'16.
  • 06/10/2016: presented work on the hardness of 2048-like games at FUN'16 in Italy.
  • 05/16/2016: attended Topological and Geometric Data Analisis (TGDA) at Ohio State University.
  • 05/06/2016: initial work on homology localization was accepted in the Young Researchers Forum of SoCG'16. Here are the abstract.
  • 04/22/2016: spoke about approximating ATSP on topologically-restricted graphs at the Capital Area Theory Seminar (CATS) [slides].
  • 04/01/2016: work on the hardness of 2048-like games has been accepted in FUN'16.
  • 01/10/2016: attended the ACM-SIAM Symposium on Discrete Algorithms (SODA16) in Crystal City, VA.
  • 11/13/2015: organized a panel titled "Getting the most out of conferences". Here's the slides (video requires login).
  • 11/04/2015: presented a demo on spatio-temporal browsing of business news in SIGSPATIAL'15.
  • 10/23/2015: Fall Workshop on Computational Geometry (FWCG'15) at SUNY Buffalo.
  • 10/10/2015: put together a prototype of an interactive tool to explore Voronoi diagrams in 3D. Check it out here.
  • 09/07/2015: research school on computational algebraic topology at the Mathematics Institute, University of Oxford.
  • 08/24/2015: work on spatio-temporal browsing of business news has been accepted in SIGSPATIAL'15.
  • 08/12/2015: presented work on the inapproximability of polygon illumination at CCCG'15 in Queens University.
  • 07/30/2015: presented work on constrained Voronoi meshing at the U.S. National Congress on Computational Mechanics.
  • 07/06/2015: 5-week visit at Sandia National Laboratories, hosted by Scott Mitchell and Mohamed Ebeida.
  • 06/22/2015: presented work on the complexity of 2048 in the Young Researchers Forum of SoCG'15 at TU Eindhoven.
  • 06/08/2015: 2-week visit at the Univeristy of Texas at Austin, hosted by Prof. Chandrajit Bajaj.
  • 05/31/2015: work on the inapproximability of polygon illumination, a variant of the art gallery problem, has been accepted in CCCG'15.
  • 04/24/2015: spoke about colorful linear programming at the Capital Area Theory Seminar (CATS).
  • 01/19/2015: winter school on convexity at Institut Henri Poincaré.
  • 01/15/2015: work on the complexity of the 2048 game is now on the arXiv. Play with the gadgets here and here.
  • 11/08/2014: Goodman-Pollack Fest/Feast at the Courant Institute of Mathematical Sciences.
  • 10/31/2014: Fall Workshop on Computational Geometry (FWCG'14) at UConn.
  • 10/26/2014: celebrating Sipser's 60's birthday at MIT.
  • 08/29/2014: completed a great summer internship at Google Research in Mountain View.
  • 08/03/2014: trying my hand at visualizing a cute geometry problem.
  • 06/08/2014: presented work on mesh simplification in the Young Researchers Forum of SoCG'14 at Kyoto University.

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