I am currently finishing my Ph.D in Computer Science at CMU, advised by Gary Miller. My research is in Computational Geometry. I am most interested in the intersection of mesh generation and computational topology.

Recently, I developed a new undergraduate course in Computational Geometry.

I am part of the Algorithms and Computational Complexity Group at CMU. Previously, I helped coordinate the weekly Theory Lunch. Now I'm just a regular attendee. I am currently managing the web page of the Low-Dimensional Manifolds Reading Group.

Outside of CS, I am involved with the CMU Filmmaking Club. I also play basketball twice a week at 12:00 at the University Center on Tuesdays and Fridays. Come by if you are looking for a game. Before coming to CMU, I was an active member of the Princeton Juggling Club.

Research

Beating the Spread: Time-Optimal Point Meshing
Gary L. Miller, Todd Phillips and Donald R. Sheehy
SOCG: ACM Symposium on Computational Geometry 2011

We present NetMesh, a new algorithm that produces a conforming Delaunay mesh for point sets in any fixed dimension with guaranteed optimal mesh size and quality. Our comparison based algorithm runs in time $O(n\log n + m)$, where $n$ is the input size and $m$ is the output size, and with constants depending only on the dimension and the desired element quality bounds. It can terminate early in $O(n\log n)$ time returning a $O(n)$ size Voronoi diagram of a superset of $P$ with a relaxed quality bound, which again matches the known lower bounds.

The previous best results in the comparison model depended on the log of the spread of the input, the ratio of the largest to smallest pairwise distance among input points. We reduce this dependence to $O(\log n)$ by using a sequence of $\epsilon$-nets to determine input insertion order in an incremental Voronoi diagram. We generate a hierarchy of well-spaced meshes and use these to show that the complexity of the Voronoi diagram stays linear in the number of points throughout the construction.

@inproceedings{miller11beating,
  Title = {Beating the Spread: Time-Optimal Point Meshing},
  Author = {Gary L. Miller and Todd Phillips and Donald R. Sheehy},
  Booktitle = {SOCG: Proceedings of the 26th ACM Symposium on Computational Geometry},
  Year = {2011}}
Topological Inference via Meshing
Benoit Hudson, Gary L. Miller, Steve Y. Oudot and Donald R. Sheehy
SOCG: ACM Symposium on Computational Geometry 2010
PDF

We apply ideas from mesh generation to improve the time and space complexities of computing the full persistent homological information associated with a point cloud $P$ in Euclidean space $R^d$. Classical approaches rely on the Cech, Rips, $\alpha$-complex, or witness complex filtrations of $P$, whose complexities scale badly with $d$. For instance, the $\alpha$-complex filtration incurs the $n^{\Omega(d)}$ size of the Delaunay triangulation, where $n$ is the size of $P$. The common alternative is to truncate the filtrations when the sizes of the complexes become prohibitive, possibly before discovering the most relevant topological features. In this paper we propose a new collection of filtrations, based on the Delaunay triangulation of a carefully-chosen superset of $P$, whose sizes are reduced to $2^{O(d^2)}n$. A nice property of these filtrations is to be interleaved multiplicatively with the family of offsets of $P$, so that the persistence diagram of $P$ can be approximated in $2^{O(d^2)}n^3$ time in theory, with a near-linear observed running time in practice. Thus, our approach remains tractable in medium dimensions, say 4 to 10.

@inproceedings{hudson10topological,
  Title = {Topological Inference via Meshing},
  Author = {Beno\^{i}t Hudson and Steve Y. Oudot and Gary L. Miller and Donald R. Sheehy},
  Booktitle = {SOCG: Proceedings of the 26th ACM Symposium on Computational Geometry},
  Year = {2010}}
The Centervertex Theorem for Wedge Depth
Gary L. Miller, Todd Phillips and Donald R. Sheehy
CCCG: The Canadian Conference in Computational Geometry 2009
PDF

There are many depth measures on point sets that yield centerpoint theorems. These theorems guarantee the existence of points of a specified depth, a kind of geometric median. However, the deep point guaranteed to exist is not guaranteed to be among the input, and often, it is not. The alpha-wedge depth of a point with respect to a point set is a natural generalization of halfspace depth that replaces halfspaces with wedges (cones or cocones) of angle $\alpha$. We introduce the notion of a centervertex, a point with depth at least $n/(d+1)$ among the set $S$. We prove that for any finite subset $S$ of $R^d$, a centervertex exists. We also present a simple algorithm for computing an approximate centervertex.

@inproceedings{miller09centervertex,
  Title = {The Centervertex Theorem for Wedge Depth},
  Author = {Gary L. Miller and Todd Phillips and Donald R. Sheehy},
  Booktitle = {CCCG: Canadian Conference in Computational Geometry},
  Year = {2009}}
Approximate Center Points with Proofs
Gary L. Miller and Donald R. Sheehy
SOCG: ACM Symposium on Computational Geometry 2009
PDF

We present the Iterated-Tverberg algorithm, the first deterministic algorithm for computing an approximate centerpoint of a set $S\in R^d$ with running time sub-exponential in $d$. The algorithm is a derandomization of the Iterated-Radon algorithm of Clarkson et al and is guaranteed to terminate with an $O(1/d^2)$-center. Moreover, it returns a polynomial-time checkable proof of the approximation guarantee, despite the coNP-Completenes of testing centerpoints in general. We also explore the use of higher order Tverberg partitions to improve the runtime of the deterministic algorithm and improve the approximation guarantee for the randomized algorithm. In particular, we show how to improve the $O(1/d^2)$- center of the Iterated-Radon algorithm to $O(1/d^{\frac{r}{r-1}})$ for a cost of $O((rd)^{d})$ in time for any integer $r$.

@inproceedings{miller09approximate,
  Title = {Approximate Center Points with Proofs},
  Author = {Gary L. Miller and Donald R. Sheehy},
  Booktitle = {SOCG: Proceedings of the 25th ACM Symposium on Computational Geometry},
  Year = {2009}}
Size Complexity of Volume Meshes vs. Surface Meshes
Benoit Hudson, Gary L. Miller, Todd Phillips and Donald R. Sheehy
SODA: ACM-SIAM Symposium on Discrete Algorithms 2009
PDF

Typical volume meshes in three dimensions are designed to conform to an underlying two-dimensional surface mesh, with volume mesh element size growing larger away from the surface. The surface mesh may be uniformly spaced or highly graded, and may have fine resolution due to extrinsic mesh size concerns. When we desire that such a volume mesh have good aspect ratio, we require that some space-filling {\it scaffold} vertices be inserted off the surface. We analyze the number of scaffold vertices in a setting that encompasses many existing volume meshing algorithms. We show that under simple preconditions, the number of scaffold vertices will be linear in the number of surface vertices.

@inproceedings{hudson09size,
  Author = {Beno\^{i}t Hudson and Gary L. Miller and Todd Phillips and Donald R. Sheehy},
  Booktitle = {SODA: ACM-SIAM Symposium on Discrete Algorithms},
  Title = {Size Complexity of Volume Meshes vs. Surface Meshes},
  Year = {2009}}
Shape Deformation in Continuous Map Generalization
Jeff Danciger, Satyan L. Devadoss, John Mugno, Donald R. Sheehy and Rachel Ward
GeoInformatica 13: 2, 203--221 2009
PDF

Given a collection of regions on a map, we seek a method of continuously altering the regions as the scale is varied. This is formalized and brought to rigor as well-defined problems in homotopic deformation. We ask the regions to preserve topology, area-ratios, and relative position as they change over time. A solution is presented using differential methods and computational geometric techniques. Most notably, an application of this method is used to provide an algorithm to obtain cartograms.

@article{danciger09shape,
  Author = {Jeff Danciger and Satyan Devadoss and John Mugno and Donald R. Sheehy and Rachel Ward},
  Journal = {GeoInformatica},
  Number = {2},
  Pages = {203--221},
  Title = {Shape Deformation in Continuous Map Generalization},
  Volume = {13},
  Year = {2009}}
Achieving Spatial Adaptivity while Finding Approximate Nearest Neighbors
Jonathan Derryberry, Daniel D. Sleator, Donald R. Sheehy and Maverick Woo
CCCG: The Canadian Conference in Computational Geometry 2008
PDF

We present the first spatially adaptive data structure that answers approximate nearest neighbor (ANN) queries to points that reside in a geometric space of any constant dimension $d$.

The $L_t$-norm approximation ratio is $O(d^{1 + 1/t})$, and the running time for a query $q$ is $O(d^2 \lg \delta(p, q))$, where $p$ is the result of the preceding query and $\delta(p, q)$ is the number of input points in a suitably-sized box containing $p$ and $q$.

Our data structure has $O(d n)$ size and requires $O(d^2 n \lg n)$ preprocessing time, where $n$ is the number of points in the data structure.

The size of the bounding box for $\delta$ depends on $d$, and our results rely on the Random Access Machine (RAM) model with word size $\Theta(\lg n)$.

@inproceedings{derryberry08achieving,
  Author = {John Derryberry and Daniel D. Sleator and Donald Sheehy and Maverick Woo},
  Booktitle = {CCCG: Canadian Conference in Computational Geometry},
  Title = {Achieving Spatial Adaptivity while Finding Approximate Nearest Neighbors},
  Year = {2008}}
Linear-size meshes
Gary L. Miller, Todd Phillips and Donald R. Sheehy
CCCG: The Canadian Conference in Computational Geometry 2008
PDF

Most modern meshing algorithms produce asymptotically optimal size output. However, the size of the optimal mesh may not be bounded by any function of $n$. In this paper, we introduce \emph{well-paced} point sets and prove that these will produce linear size outputs when meshed with any ``size-optimal'' meshing algorithm. This work generalizes all previous work on the linear cost of balancing quadtrees. We also present an algorithm that uses well-paced points to produce a linear size Delaunay mesh of a point set in $R^d$.

@inproceedings{miller08linear,
  Author = {Gary L. Miller and Todd Phillips and Donald R. Sheehy},
  Booktitle = {CCCG: Canadian Conference in Computational Geometry},
  Title = {Linear-size meshes},
  Year = {2008}}
Size Competitive Meshing without Large Angles
Gary L. Miller, Todd Phillips and Donald R. Sheehy
ICALP: 34th International Colloquium on Automata, Languages and Programming 2007
PDF

We present a new meshing algorithm for the plane, Overlay Stitch Meshing (OSM), accepting as input an arbitrary Planar Straight Line Graph and producing a triangulation with all angles smaller than $170^\circ$. The output triangulation has competitive size with any optimal size mesh having equally bounded largest angle. The competitive ratio is $O(\log(L/s))$ where $L$ and $s$ are respectively the largest and smallest features in the input. OSM runs in $O(n \log (L/s) + m)$ time/work where $n$ is the input size and $m$ is the output size. The algorithm first uses Sparse Voronoi Refinement to compute a quality overlay mesh of the input points alone. This triangulation is then combined with the input edges to give the final mesh.

@inproceedings{miller07size,
  Author = {Gary L. Miller and Todd Phillips and Donald R. Sheehy},
  Booktitle = {34th International Colloquium on Automata, Languages and Programming},
  Title = {Size Competitive Meshing without Large Angles},
  Year = {2007}}
Compatible Triangulations and Point Partitions by Series Triangular Graphs
Jeff Danciger, Satyan L. Devadoss and Donald R. Sheehy
Computational Geometry: Theory and Applications 34, 195--202 2006
PDF

We introduce series-triangular graph embeddings and show how to partition point sets with them. This result is then used to prove an upper bound on the number of Steiner points needed to obtain compatible triangulations of point sets. The problem is generalized to finding compatible triangulations for more than two point sets and we show that such triangulations can be constructed with only a linear number of Steiner points added to each point set. Moreover, the compatible triangulations constructed by these methods are regular triangulations.

@article{danciger06compatible,
  Author = {Jeff Danciger and Satyan Devadoss and Donald R. Sheehy},
  Journal = {Computational Geometry: Theory and Applications},
  Pages = {195--202},
  Title = {Compatible Triangulations and Point Partitions by Series Triangular Graphs},
  Volume = {34},
  Year = {2006}}

Other Papers

  1. Fat Voronoi Diagrams
    Gary L. Miller, Todd Phillips and Donald R. Sheehy
    The Fall Workshop in in Computational Geometry 2010
    PDF
    @inproceedings{miller10fat,
      Author = {Gary L. Miller and Todd Phillips and Donald R. Sheehy},
      Booktitle = {The Fall Workshop in Computational Geometry},
      Title = {Multi-Filtering Noise for Geometric Persistent Homology},
      Year = {2010}}
  2. (Multi)Filtering Noise in Geometric Persistent Homology
    Donald R. Sheehy
    The Fall Workshop in in Computational Geometry 2010
    PDF
    @inproceedings{sheehy10multifiltering,
      Author = {Donald R. Sheehy},
      Booktitle = {The Fall Workshop in Computational Geometry},
      Title = {(Multi)Filtering Noise in Geometric Persistent Homology},
      Year = {2010}}
  3. Mesh-Enhanced Persistent Homology
    Benoit Hudson, Gary L. Miller, Steve Y. Oudot and Donald R. Sheehy
    The Fall Workshop in in Computational Geometry 2009
    PDF
    @inproceedings{hudson09mesh-fwcg,
      Author = {Beno\^{i}t Hudson and Gary L. Miller and Steve Y. Oudot and Donald R. Sheehy},
      Booktitle = {The Fall Workshop in Computational Geometry},
      Title = {Mesh-Enhanced Persistent Homology},
      Year = {2009}}
  4. Approximating Voronoi Diagrams with Voronoi Diagrams
    Gary L. Miller, Todd Phillips and Donald R. Sheehy
    The Fall Workshop in in Computational Geometry 2009
    PDF
    @inproceedings{miller09approximating,
      Author = {Gary L. Miller and Todd Phillips and Donald R. Sheehy},
      Booktitle = {The Fall Workshop in Computational Geometry},
      Title = {Approximating Voronoi Diagrams with Voronoi Diagrams},
      Year = {2009}}
  5. Fast sizing calculations for meshing
    Gary L. Miller, Todd Phillips and Donald R. Sheehy
    The Fall Workshop in in Computational Geometry 2008
    PDF
    @inproceedings{miller08fast,
      Author = {Gary L. Miller and Todd Phillips and Donald R. Sheehy},
      Booktitle = {The Fall Workshop in Computational Geometry},
      Title = {Fast sizing calculations for meshing},
      Year = {2008}}
  6. Cone Depth and the Center Vertex Theorem
    Gary L. Miller, Todd Phillips and Donald R. Sheehy
    The Fall Workshop in in Computational Geometry 2008
    PDF
    @inproceedings{miller08cone,
      Author = {Gary L. Miller and Todd Phillips and Donald R. Sheehy},
      Booktitle = {The Fall Workshop in Computational Geometry},
      Title = {Cone Depth and the Center Vertex Theorem},
      Year = {2008}}
  7. The Complexity of Domino Tiling Problems
    Donald R. Sheehy
    Undergraduate Independent Research 2005
    PDF

Talks

  1. Beating the Spread: Time-Optimal Point Meshing
    Presented at Symposium on Computational Geometry, 2011, Paris, France

    We present NetMesh, a new algorithm that produces a conforming Delaunay mesh for point sets in any fixed dimension with guaranteed optimal mesh size and quality. Our comparison based algorithm runs in time $O(n\log n + m)$, where $n$ is the input size and $m$ is the output size, and with constants depending only on the dimension and the desired element quality bounds. It can terminate early in $O(n\log n)$ time returning a $O(n)$ size Voronoi diagram of a superset of $P$ with a relaxed quality bound, which again matches the known lower bounds.

    The previous best results in the comparison model depended on the log of the spread of the input, the ratio of the largest to smallest pairwise distance among input points. We reduce this dependence to $O(\log n)$ by using a sequence of $\epsilon$-nets to determine input insertion order in an incremental Voronoi diagram. We generate a hierarchy of well-spaced meshes and use these to show that the complexity of the Voronoi diagram stays linear in the number of points throughout the construction.

  2. Learning with Nets and Meshes
    Computational Geometry Learning Workshop (CGL), Paris, France

    In this talk, I argue that mesh generation is good tool to preprocess point clouds for geometric inference and discuss how to compute such meshes.

  3. Meshes and Nets
    Presented at CMU Theory Lunch, April 6, 2011

    What is the difference between a mesh and a net? What is the difference between a metric space epsilon-net and a range space epsilon-net? What is the difference between geometric divide-and-conquer and combinatorial divide-and-conquer?
    In this talk, I will answer these questions and discuss how these different ideas come together to finally settle the question of how to compute conforming point set meshes in optimal time. The meshing problem is to discretize space into as few pieces as possible and yet still capture the underlying density of the input points. Meshes are fundamental in scientific computing, graphics, and more recently, topological data analysis.
    This is joint work with Gary Miller and Todd Phillips

  4. Ball Packings and Fat Voronoi Diagrams
    Presented at CMU Theory Lunch, September 15, 2010

    Here's a toy problem: What is the SMALLEST number of unit balls you can fit in a box such that no more will fit? In this talk, I will show how just thinking about a naive greedy approach to this problem leads to a simple derivation of several of the most important theoretical results in the field of mesh generation. We'll prove classic upper and lower bounds on both the number of balls and the complexity of their interrelationships.

    Then, we'll relate this problem to a similar one called the Fat Voronoi Problem, in which we try to find point sets such that every Voronoi cell is fat (the ratio of the radii of the largest contained to smallest containing ball is bounded). This problem has tremendous promise in the future of mesh generation as it can circumvent the classic lowerbounds presented in the first half of the talk. Unfortunately the simple approach no longer works. In the end we will show that the number of neighbors of any cell in a Fat Voronoi Diagram in the plane is bounded by a constant (if you think that's obvious, spend a minute to try to prove it). We'll also talk a little about the higher dimensional version of the problem and its wide range of applications.

  5. Topological Inference via Meshing
    Presented at Symposium on Computational Geometry, 2010, in Snowbird, Utah

    In topological inference, the goal is to extract information about a shape, given only a sample of points from it. There are many approaches to this problem, but the one we focus on is persistent homology. We get a view of the data at different scales by imagining the points are balls and consider different radii. The shape information we want comes in the form of a persistence diagram, which describes the components, cycles, bubbles, etc in the space that persist over a range of different scales. To actually compute a persistence diagram in the geometric setting, previous work required complexes of size n^O(d). We reduce this complexity to O(n) (hiding some large constants depending on d) by using ideas from mesh generation. This talk will not assume any knowledge of topology. This is joint work with Gary Miller, Benoit Hudson, and Steve Oudot.

  6. Topological Inference via Meshing (long version for Theory Lunch)
    Presented at CMU Theory Lunch, March 3, 2010

    In topological inference, the goal is to extract information about a shape, given only a sample of points from it. There are many approaches to this problem, but the one we focus on is persistent homology. We get a view of the data at different scales by imagining the points are balls and consider different radii. The shape information we want comes in the form of a persistence diagram, which describes the components, cycles, bubbles, etc in the space that persist over a range of different scales. To actually compute a persistence diagram in the geometric setting, previous work required complexes of size n^O(d). We reduce this complexity to O(n) (hiding some large constants depending on d) by using ideas from mesh generation. This talk will not assume any knowledge of topology. This is joint work with Gary Miller, Benoit Hudson, and Steve Oudot.

  7. Prospective Students Research Talk:
    Geometry, Topology and All of You Wildest Dreams Will Come True.
    Presented to CMU Prospective Grad Students, Feb 27, 2010

    In this light talk, I give a high level view of some of my recent research in using ideas from mesh generation to lower the complexity of computing persistent homology in geomemtric settings. Because this talk is for a general audience, I will focus on three related applications (where related is interpreted loosely) that I think have the widest appeal. The applications are: (1) Winning Nobel Peace Prizes, (2)Winning Olympic Gold Medals, and (3) Finding True Love

  8. The Centervertex Theorem for Wedge Depth
    Presented at the Canadian Conference on Computational Geometry, 2009, in Vancouver

    There are many depth measures on point sets that yield centerpoint theorems. These theorems guarantee the existence of points of a specified depth, a kind of geometric median. However, the deep point guaranteed to exist is not guaranteed to be among the input, and often, it is not. The alpha-wedge depth of a point with respect to a point set is a natural generalization of halfspace depth that replaces halfspaces with wedges (cones or cocones) of angle alpha. We introduce the notion of a centervertex, a point with depth at least n/(d+1) among the set S. We prove that for any finite subset S of R^d, a centervertex exists. We also present a simple algorithm for computing an approximate centervertex.

  9. Approximate Centerpoints with Proofs
    Presented at the Symposium on Computational Geometry, 2009, in Aarhus, Denmark.

    We show how to derandomize the Iterated-Radon algorithm to achieve the first deterministic algorithm for computing approximate centerpoints that runs in time subexponential in the dimension. The algorithm also returns a polynomial-time checkable proof of the quality of the returned centerpoint.

  10. Planar Graphs in 2 1/2 Dimensions
    Presented at Theory Lunch, Carnegie Mellon University, March 18, 2009

    In 1864, James Clerk Maxwell published his now famous correspondence between equilibrium stresses and liftings of planar graphs into 3D "terrains." We will explore this classic theorem and how it has influenced many areas of modern theoretical computer science. This survey will touch on results in graph drawing, regular triangulations, network routing, rigidity theory, and spectral graph theory (time permitting).

  11. Linear-size meshes
    Presented at the Canadian Conference on Computational Geometry, 2008, in Montreal

    We show how to adapt Delaunay refinement meshing technology to produce linear size Delaunay meshes of any input point set. The new technique that makes this possible is the use of well-paced points, or those that can be ordered so that consecutive prefixes have a bounded difference in local feature size.

  12. Achieving Spatial Adaptivity while Finding Approximate Nearest Neighbors
    Presented at the Canadian Conference on Computational Geometry, 2008, in Montreal

    We give an algorithm for computing approximate nearest neighbors that also achieves spatial adaptivity, a kind of geometric finger search. The algorithm is general dimensional.

  13. Cone Depth and the Center Vertex Theorem
    Presented at The Fall Workshop in in Computational Geometry, October 31, 2008

    We generalize the Tukey depth to use cones instead of halfspaces. We prove a generalization of the Center Point Theorem that for $S\subset \reals^d$, there is a vertex $s\in S$, with depth at least $\frac{n}{d+1}$ for cones of half-angle $45^\circ$. This gives a notion of data depth for which an approximate median can always be found among the original set. We present a simple algorithm for computing an approximate center vertex.

  14. Searching for the Center
    Presented at Theory Lunch, Carnegie Mellon University, October 8, 2008

    Convexity is a powerful tool for extracting combinatorial information from geometric objects. In this talk, I will survey several classical convexity theorems going back to the 1920s and show how they are useful in computational geometry today. In particular, I will focus on the problem of computing center points. A center point p for a set S is a point such that any line through p divides S evenly (at worst its a 1/3-2/3 cut). The existence of a center point follows independently from both Helly's Theorem (1923) and Tverberg's Theorem (1966). By borrowing intuition from both theorems, we arrive at a new deterministic algorithm for computing approximate center points in higher dimensions.

  15. A Competitive Algorithm for No-Large-Angle Triangulation
    Presented at Theory Lunch, Carnegie Mellon University, May 2, 2007

    In this talk, I will present Overlay Stitch Meshing, a novel new algorithm that simultaneously solves two different problems in the field of triangulating planar straight-line graphs in the plane for scientific computing applications: It is the first Delaunay Refinement-type triangulation algorithm that terminates with a full complement of guarantees even on degenerate inputs and with no dependence on the size of the smallest input angle. It is the first algorithm that gives a log competitive output size for the problem of no-large-angle triangulation with Steiner points. The workings of the algorithm are very easy to state and understand. The brunt of the talk will focus on new analytic techniques that allow us to prove strong guarantees.

  16. Flips in Computational Geometry
    Presented at Theory Lunch, Carnegie Mellon University, Nov. 15, 2006

    In this talk, we will be looking at a basic primitive in computational geometry, the flip. Also known as bistellar flips, edge-flips, rotations, and Pachner moves, this local change operation has been discovered and rediscovered in a variety of fields (thus the many names) and has proven useful both as an algorithmic tool as well as a proof technology. For algorithm designers working outside of computational geometry, one can consider the flip move as a higher dimensional analog of the tree rotations used in binary trees. I will survey some of the most important results about flips with an emphasis on developing a general geometric intuition that has led to many advances.