Graduate Student

Computer Science

Carnegie Mellon University

9219 Gates Hall

dsheehy@cs.cmu.edu


I am in my fifth year as a graduate student 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.

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 served as webmaster for their recent Rack Focus Film Festival. 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

    2009

  1. The Centervertex Theorem for Wedges
    Gary L. Miller, Todd Phillips, 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 Wedges},
    Author = {Gary L. Miller and Todd Phillips and Donald Sheehy},
    Booktitle = {CCCG: Canadian Conference in Computational Geometry},
    Year = {2009}}

  2. Approximate Center Points with Proofs
    Gary L. Miller, 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 Sheehy},
    Booktitle = {SOCG: Proceedings of the 25th ACM Symposium on Computational Geometry},
    Year = {2009}}

  3. Size Complexity of Volume Meshes vs. Surface Meshes
    Benoit Hudson, Gary L. Miller, Todd Phillips, 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 Sheehy},
    Booktitle = {SODA: ACM-SIAM Symposium on Discrete Algorithms},
    Title = {Size Complexity of Volume Meshes vs. Surface Meshes},
    Year = {2009}}

  4. Shape Deformation in Continuous Map Generalization
    Jeff Danciger, Satyan L. Devadoss, John Mugno, Donald R. Sheehy, Rachel Ward,
    GeoInformatica 13 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 Sheehy and Rachel Ward},
    Journal = {GeoInformatica},
    Number = {2},
    Pages = {203--221},
    Title = {Shape Deformation in Continuous Map Generalization},
    Volume = {13},
    Year = {2009}}

  5. 2008

  6. Achieving Spatial Adaptivity while Finding Approximate Nearest Neighbors
    Jonathan Derryberry, Daniel D. Sleator, Donald R. Sheehy, 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}}

  7. Linear-size meshes
    Gary L. Miller, Todd Phillips, 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 Sheehy},
    Booktitle = {CCCG: Canadian Conference in Computational Geometry},
    Title = {Linear-size meshes},
    Year = {2008}}

  8. Fast sizing calculations for meshing
    Gary L. Miller, Todd Phillips, Donald R. Sheehy,
    The Fall Workshop in in Computational Geometry 2008
    PDF

    Not availiable

    @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}}

  9. Cone Depth and the Center Vertex Theorem
    Gary L. Miller, Todd Phillips, Donald R. Sheehy,
    The Fall Workshop in in Computational Geometry 2008
    PDF

    Not availiable

    @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}}

  10. 2007

  11. Size Competitive Meshing without Large Angles
    Gary L. Miller, Todd Phillips, 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 Sheehy},
    Booktitle = {34th International Colloquium on Automata, Languages and Programming},
    Title = {Size Competitive Meshing without Large Angles},
    Year = {2007}}

  12. 2006

  13. Compatible Triangulations and Point Partitions by Series Triangular Graphs
    Jeff Danciger, Satyan L. Devadoss, 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 Sheehy},
    Journal = {Computational Geometry: Theory and Applications},
    Pages = {195--202},
    Title = {Compatible Triangulations and Point Partitions by Series Triangular Graphs},
    Volume = {34},
    Year = {2006}}

  14. 2005

  15. The Complexity of Domino Tiling Problems
    Donald R. Sheehy,
    Undergraduate Independent Research 2005
    PDF

Talks

  1. 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.
  2. 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.
  3. 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).
  4. 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.
  5. 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.
  6. 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.
  7. 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.
  8. 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:
    1. 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.
    2. 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.
  9. 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.