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.
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}}
SOCG: ACM Symposium on Computational Geometry 2010
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}}
CCCG: The Canadian Conference in Computational Geometry 2009
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}}
SOCG: ACM Symposium on Computational Geometry 2009
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}}
SODA: ACM-SIAM Symposium on Discrete Algorithms 2009
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}}
GeoInformatica 13: 2, 203--221 2009
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}}
CCCG: The Canadian Conference in Computational Geometry 2008
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}}
CCCG: The Canadian Conference in Computational Geometry 2008
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}}
ICALP: 34th International Colloquium on Automata, Languages and Programming 2007
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}}
Computational Geometry: Theory and Applications 34, 195--202 2006
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}}
-
Fat Voronoi Diagrams
The Fall Workshop in in Computational Geometry 2010@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}} -
(Multi)Filtering Noise in Geometric Persistent Homology
The Fall Workshop in in Computational Geometry 2010@inproceedings{sheehy10multifiltering, Author = {Donald R. Sheehy}, Booktitle = {The Fall Workshop in Computational Geometry}, Title = {(Multi)Filtering Noise in Geometric Persistent Homology}, Year = {2010}} -
Mesh-Enhanced Persistent Homology
The Fall Workshop in in Computational Geometry 2009@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}} -
Approximating Voronoi Diagrams with Voronoi Diagrams
The Fall Workshop in in Computational Geometry 2009@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}} -
Fast sizing calculations for meshing
The Fall Workshop in in Computational Geometry 2008@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}} -
Cone Depth and the Center Vertex Theorem
The Fall Workshop in in Computational Geometry 2008@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}}
-
Beating the Spread: Time-Optimal Point MeshingPresented 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. -
Learning with Nets and MeshesComputational 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.
-
Meshes and NetsPresented 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 -
Ball Packings and Fat Voronoi DiagramsPresented 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. -
Topological Inference via MeshingPresented 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.
-
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.
-
Prospective Students Research Talk:
Geometry, Topology and All of You Wildest Dreams Will Come True.Presented to CMU Prospective Grad Students, Feb 27, 2010In 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
-
The Centervertex Theorem for Wedge DepthPresented 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.
-
Approximate Centerpoints with ProofsPresented 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.
-
Planar Graphs in 2 1/2 DimensionsPresented 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).
-
Linear-size meshesPresented 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.
-
Achieving Spatial Adaptivity while Finding Approximate Nearest NeighborsPresented 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.
-
Cone Depth and the Center Vertex TheoremPresented 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.
-
Searching for the CenterPresented 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.
-
A Competitive Algorithm for No-Large-Angle TriangulationPresented 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.
-
Flips in Computational GeometryPresented 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.