I am an Assistant Professor of Computer Science at the University of Connecticut. My research is in geometric algorithms. I am most interested in the intersection of geometric algorithms and topological data analysis.

Watch the video of my talk on Sensors and Samples: A Homological Approach at the Institute for Advanced Study Workshop on Topology. Here is a talk I gave on Mesh Generation and Topological Data Analysis.

# Research

Frechet-Stable Signatures Using Persistent Homology
Donald R. Sheehy
SODA: ACM-SIAM Symposium on Discrete Algorithms 2018

For a metric space $Y$, the Frechet distance is a metric on trajectories $f,g:[0,1]\to Y$ that minimizes $\max_{t\in [0,1]}d_Y(f(t), g(h(t)))$ over continuous reparameterizations $h$ of time. One can define the generalized Frechet distance between more complex objects, functions $f:X\to Y$ where $X$ is some topological space that minimizes over homeomorphisms from $X\to X$. This more general definition has been studied for surfaces and often leads to computationally hard problems. We show how to compute in polynomial-time signatures for these functions for which the resulting metric on the signatures can also be computed in polynomial-time and provides a meaningful lower bound on the generalized Frechet distance. Our approach uses persistent homology and exploits the natural invariance of persistence diagrams of functions to homeomorphisms of the domain. Our algorithm for computing the signatures in Euclidean spaces uses a new method for computing persistent homology of convex functions on simplicial complexes which may be of independent interest.

@inproceedings{sheehy18frechet,
Author = {Donald R. Sheehy},
Booktitle = {Proceedings of the ACM-SIAM Symposium on Discrete Algorithms},
Title = {Fr\'{e}chet-Stable Signatures Using Persistent Homology},
Year = {2018}}
Supporting Ruled Polygons
Nicholas J. Cavanna, Marc Khoury, and Donald R. Sheehy
CCCG: The Canadian Conference in Computational Geometry 2017

We explore several problems related to ruled polygons. Given a ruling of a polygon P, we consider the Reeb graph of P induced by the ruling. We define the Reeb complexity of P, which roughly equates to the minimum number of points necessary to support P. We give asymptotically tight bounds on the Reeb complexity that are also tight up to a small additive constant. When restricted to the set of parallel rulings, we show that the Reeb complexity can be computed in polynomial time.

@inproceedings{cavanna17supporting,
Author = {Nicholas J. Cavanna and Marc Khoury and Donald R. Sheehy},
Booktitle = {Proceedings of the Canadian Conference on Computational Geometry},
Title = {Supporting Ruled Polygons},
Year = {2017}}
When and Why the Topological Coverage Criterion Works
Nicholas J. Cavanna, Kirk Gardner, and Donald R. Sheehy
SODA: ACM-SIAM Symposium on Discrete Algorithms 2017

In their seminal work on homological sensor networks, de Silva and Ghrist showed the surprising fact that it’s possible to certify the coverage of a coordinate-free sensor network even with very minimal knowledge of the space to be covered. Here, coverage means that every point in the domain (except possibly those very near the boundary) has a nearby sensor. More generally, their algorithm takes a pair of nested neighborhood graphs along with a labeling of vertices as either boundary or interior and computes the relative homology of a simplicial complex induced by the graphs. This approach, called the Topological Coverage Criterion (TCC), requires some assumptions about the underlying geometric domain as well as some assumptions about the relationship of the input graphs to the domain. The goal of this paper is to generalize these assumptions and show how the TCC can be applied to both much more general domains as well as very weak assumptions on the input. We give a new, simpler proof of the de Silva-Ghrist Topological Coverage Criterion that eliminates any assumptions about the smoothness of the boundary of the underlying space, allowing the results to be applied to much more general problems. The new proof factors the geometric, topological, and combinatorial aspects, allowing us to provide a coverage condition that supports thick boundaries, k-coverage, and weighted coverage, in which sensors have varying radii.

@inproceedings{cavanna17when,
Author = {Nicholas J. Cavanna and Kirk P. Gardner and Donald R. Sheehy},
Booktitle = {Proceedings of the ACM-SIAM Symposium on Discrete Algorithms},
Title = {When and Why the Topological Coverage Criterion Works},
Year = {2017}}
Efficient and Robust Persistent Homology for Measures
Mickael Buchet, Frederic Chazal, Steve Y. Oudot, and Donald R. Sheehy
Computational Geometry: Theory and Applications. 58: 70-96 2016

A new paradigm for point cloud data analysis has emerged recently, where point clouds are no longer treated as mere compact sets but rather as empirical measures. A notion of distance to such measures has been defined and shown to be stable with respect to perturbations of the measure. This distance can easily be computed pointwise in the case of a point cloud, but its sublevel-sets, which carry the geometric information about the measure, remain hard to compute or approximate. This makes it challenging to adapt many powerful techniques based on the Euclidean distance to a point cloud to the more general setting of the distance to a measure on a metric space. We propose an efficient and reliable scheme to approximate the topological structure of the family of sublevel-sets of the distance to a measure. We obtain an algorithm for approximating the persistent homology of the distance to an empirical measure that works in arbitrary metric spaces. Precise quality and complexity guarantees are given with a discussion on the behavior of our approach in practice.

@article{buchet16efficient,
Title = {Efficient and Robust Persistent Homology for Measures},
Author = {Micka\"{e}l Buchet and Fr\'{e}d\'{e}ric Chazal and Steve Y. Oudot and Donald Sheehy},
Booktitle = {Computational Geometry: Theory and Applications},
Volume = {58}
Pages = {70--96}
Year = {2016}}
Transforming Hierarchical Trees on Metric Spaces
Mahmoodreza Jahanseir, and Donald R. Sheehy
CCCG: The Canadian Conference in Computational Geometry 2016

We show how a simple hierarchical tree called a cover tree can be turned into an asymptotically more efficient one known as a net-tree in linear time. We also introduce two linear-time operations to manipulate cover trees called coarsening and refining. These operations make a trade-off between tree height and the node degree.

@inproceedings{jahanseir16transforming,
Author = {Mahmoodreza Jahanseir and Donald R. Sheehy},
Booktitle = {Proceedings of the Canadian Conference on Computational Geometry},
Title = {Transforming Hierarchical Trees on Metric Spaces},
Year = {2016}}
$k$th Nearest Neighbor Sampling in the Plane
Kirk Gardner, and Donald R. Sheehy
CCCG: The Canadian Conference in Computational Geometry 2016

Let $B$ be a square region in the plane. We give an efficient algorithm that takes a set $P$ of $n$ points from $B$, and produces a set $M\subset B$ with the property that the distance to the second nearest point in $M$ approximates the distance to the $k$th nearest point of $P$. That is, there are constants $\alpha, \beta\in \mathbb{R}$ such that for all $x\in B$, we have $\alpha\mathrm{d}_{P,k}(x) \le \mathrm{d}_{M,2}(x) \le \beta \mathrm{d}_{P,k}(x)$, where $\mathrm{d}_{M,2}$ and $\mathrm{d}_{P,k}$ denote the second nearest and $k$th nearest neighbor distance functions to $M$ and $P$ respectively. The algorithm is based on Delaunay refinement. The output set $M$ also has the property that its Delaunay triangulation has a lower bound on the size of the smallest angle. The primary application is in statistical density estimation and robust geometric inference.

@inproceedings{gardner16kth,
Author = {Kirk P. Gardner and Donald R. Sheehy},
Booktitle = {Proceedings of the Canadian Conference on Computational Geometry},
Title = {$k$th Nearest Neighbor Sampling in the Plane},
Year = {2016}}
Nicholas J. Cavanna, and Donald R. Sheehy
CCCG: The Canadian Conference in Computational Geometry 2016

We generalize the local-feature size definition of adaptive sampling used in surface reconstruction to relate it to an alternative metric on Euclidean space. In the new metric, adaptive samples become uniform samples, making it simpler both to give adaptive sampling versions of homological inference results and to prove topological guarantees using the theory of critical points to distance functions.

@inproceedings{cavanna16adaptive,
Author = {Nicholas J. Cavanna and Donald R. Sheehy},
Booktitle = {Proceedings of the Canadian Conference on Computational Geometry},
Year = {2016}}
Exploring Circle Packing Algorithms
Kevin Pratt, Connor Riley, and Donald R. Sheehy
SOCG: Symposium on Computational Geometry (Multimedia Session) 2016

We present a new tool for interactively building and evaluating circle packings of planar graphs.

@inproceedings{pratt16exploring,
Author = {Kevin Pratt and Connor Riliey and Donald R. Sheehy},
Booktitle = {Proceedings of the 32st International Symposium on Computational Geometry},
Title = {Exploring Circle Packing Algorithms},
Year = {2016}}
Interactive Geometric Algorithm Visualization in a Browser
Lynn Asselin, Kirk Gardner, and Donald R. Sheehy
SOCG: Symposium on Computational Geometry (Multimedia Session) 2016

We present an open source computational geometry framework with interactive visualizations. We provide code for simple topological data structures that can describe planar geometry, polyhedral surfaces, and even more complex topological surfaces. Because the data structures use the same simple primitives for all levels of complexity, it provides a natural springboard for students, educators, and developers. See compugeom.github.io for an interactive demo.

@inproceedings{asselin16interactive,
Author = {Lynn Asselin and Kirk P. Gardner and Donald R. Sheehy},
Booktitle = {Proceedings of the 32st International Symposium on Computational Geometry},
Title = {Interactive Geometric Algorithm Visualization in a Browser},
Year = {2016}}
Persistent Homology and Nested Dissection
Michael Kerber, Donald R. Sheehy, and Primoz Skraba
SODA: ACM-SIAM Symposium on Discrete Algorithms 2016

Nested dissection exploits the underlying topology to do matrix reductions while persistent homology exploits matrix reductions to the reveal underlying topology. It seems natural that one should be able to combine these techniques to beat the currently best bound of matrix multiplication time for computing persistent homology. However, nested dissection works by fixing a reduction order, whereas persistent homology generally constrains the ordering according to an input filtration. Despite this obstruction, we show that it is possible to combine these two theories. This shows that one can improve the computation of persistent homology if the underlying space has some additional structure. We give reasonable geometric conditions under which one can beat the matrix multiplication bound for persistent homology.

@inproceedings{kerber16persistent,
Author = {Michael Kerber and Donald R. Sheehy and Primoz Skraba},
Booktitle = {Proceedings of the ACM-SIAM Symposium on Discrete Algorithms},
Title = {Persistent Homology and Nested Dissection},
Year = {2016}}
Zigzag Zoology: Rips Zigzags for Homology Inference
Steve Y. Oudot, and Donald R. Sheehy
Foundations of Computational Mathematics 2015

For points sampled near a compact set $X$, the persistence barcode of the Rips filtration built from the sample contains information about the homology of $X$ as long as $X$ satisfies some geometric assumptions. The Rips filtration is prohibitively large, however zigzag persistence can be used to keep the size linear. We present several species of Rips-like zigzags and compare them with respect to the signal-to-noise ratio, a measure of how well the underlying homology is represented in the persistence barcode relative to the noise in the barcode at the relevant scales. Some of these Rips-like zigzags have been available as part of the Dionysus library for several years while others are new. Interestingly, we show that some species of Rips zigzags will exhibit less noise than the (non-zigzag) Rips filtration itself. Thus, the Rips zigzag can offer improvements in both size complexity and signal-to-noise ratio.

Along the way, we develop new techniques for manipulating and comparing persistence barcodes from zigzag modules. We give methods for reversing arrows and removing spaces from a zigzag. We also discuss factoring zigzags and a kind of interleaving of two zigzags that allows their barcodes to be compared. These techniques were developed to provide our theoretical analysis of the signal-to-noise ratio of Rips-like zigzags, but they are of independent interest as they apply to zigzag modules generally.

@article{oudot15zigzag,
Title = {Zigzag Zoology: Rips Zigzags for Homology Inference},
Author = {Steve Y. Oudot and Donald R. Sheehy},
Booktitle = {Foundations of Computational Mathematics},
Pages = {1151--1186},
Year = {2015}}
An Output-Sensitive Algorithm for Computing Weighted $\alpha$-Complexes
Donald R. Sheehy
CCCG: The Canadian Conference in Computational Geometry 2015

An $\alpha$-complex is a subcomplex of the Delaunay triangulation of a point set $P\subset \mathbb{R}^d$ that is topologically equivalent to the union of balls of radius $\alpha$ centered at the points of $P$. In this paper, we give an output-sensitive algorithm to compute $\alpha$-complexes of $n$-point sets in constant dimensions, whose running time is $O(f\log n\log \frac{\alpha}{s})$, where $s$ is the smallest pairwise distance and $f$ is the number of simplices in the $c\alpha$-complex for a constant $c$. The algorithm is based on a refinement of a recent algorithm for computing the full Delaunay triangulation of $P$. We also extend the algorithm to work with weighted points provided the weights are appropriately bounded. The new analysis, which may be of independent interest, bounds the number of intersections of $k$-faces of a Voronoi diagram with $(d-k)$-faces of the Voronoi diagram of a carefully constructed superset.

@inproceedings{sheehy15output,
Author = {Donald R. Sheehy},
Booktitle = {Proceedings of the Canadian Conference on Computational Geometry},
Title = {An Output-Sensitive Algorithm for Computing Weighted $\alpha$-Complexes},
Year = {2015}}
A Geometric Perspective on Sparse Filtrations
Nicholas J. Cavanna, Mahmoodreza Jahanseir, and Donald R. Sheehy
CCCG: The Canadian Conference in Computational Geometry 2015

We present a geometric perspective on sparse filtrations used in topological data analysis. This new perspective leads to much simpler proofs, while also being more general, applying equally to Rips filtrations and Cech filtrations for any convex metric. We also give an algorithm for finding the simplices in such a filtration and prove that the vertex removal can be implemented as a sequence of elementary edge collapses.

@inproceedings{cavanna15geometric,
Author = {Nicholas J. Cavanna and Mahmoodreza Jahanseir and Donald R. Sheehy},
Booktitle = {Proceedings of the Canadian Conference on Computational Geometry},
Title = {A Geometric Perspective on Sparse Filtrations},
Year = {2015}}
Approximating Nearest Neighbor Distances
Michael B. Cohen, Brittany Terese Fasy, Gary L. Miller, Amir Nayyeri, Donald R. Sheehy, and Ameya Velingker
WADS: Algorithms and Data Structures Symposium 2015

Several researchers proposed using non-Euclidean metrics on point sets in Euclidean space for clustering noisy data. Almost always, a distance function is desired that recognizes the closeness of the points in the same cluster, even if the Euclidean cluster diameter is large. Therefore, it is preferred to assign smaller costs to the paths that stay close to the input points. In this paper, we consider a natural metric with this property, which we call the nearest neighbor metric. Given a point set~$P$ and a path~$\gamma$, this metric is the integral of the distance to $P$ along $\gamma$. We describe a \mbox{$(3+\varepsilon)$}-approximation algorithm and a more intricate $(1+\varepsilon)$-approximation algorithm to compute the nearest neighbor metric. Both approximation algorithms work in near-linear time. The former uses shortest paths on a sparse graph defined over the input points. The latter uses a sparse sample of the ambient space, to find good approximate geodesic paths.

@inproceedings{cohen15approximating,
Author = {Michael B. Cohen and Brittany Terese Fasy and Gary L. Miller and Amir Nayyeri and Donald R. Sheehy and Ameya Velingker},
Booktitle = {Proceedings of the Algorithms and Data Structures Symposium},
Date-Modified = {2015-07-31 02:23:04 +0000},
Title = {Approximating Nearest Neighbor Distances},
Year = {2015}}
Visualizing Sparse Filtrations
Nicholas J. Cavanna, Mahmoodreza Jahanseir, and Donald R. Sheehy
SOCG: Symposium on Computational Geometry (Multimedia Session) 2015

Over the last few years, there have been several approaches to building sparser complexes that still give good approximations to the persistent homology. In this video, we have illustrated a geometric perspective on sparse filtrations that leads to simpler proofs, more general theorems, and a more visual explanation. We hope that as these techniques become easier to understand, they will also become easier to use.
Visualizing Sparse Filtrations from Don Sheehy on Vimeo.

@inproceedings{cavanna15visualizing,
Author = {Nicholas J. Cavanna and Mahmoodreza Jahanseir and Donald R. Sheehy},
Booktitle = {Proceedings of the 31st International Symposium on Computational Geometry},
Title = {Visualizing Sparse Filtrations},
Year = {2015}}
The Persistent Homology of Distance Functions under Random Projection
Donald R. Sheehy
SOCG: Symposium on Computational Geometry 2014

Given $n$ points $P$ in a Euclidean space, the Johnson-Lindenstrauss lemma guarantees that the distances between pairs of points is preserved up to a small constant factor with high probability by random projection into $O(\log n)$ dimensions. In this paper, we show that the persistent homology of the distance function to $P$ is also preserved up to a comparable constant factor. One could never hope to preserve the distance function to $P$ pointwise, but we show that it is preserved sufficiently at the critical points of the distance function to guarantee similar persistent homology. We prove these results in the more general setting of weighted $k$th nearest neighbor distances, for which $k=1$ and all weights equal to zero gives the usual distance to $P$.

@inproceedings{sheehy14persistent,
Title = {The Persistent Homology of Distance Functions under Random Projection},
Author = {Donald R. Sheehy},
Booktitle = {Proceedings of the 30th annual Symposium on Computational Geometry},
Year = {2014}}
A new approach to output-sensitive construction of Voronoi diagrams and Delaunay triangulations
Gary L. Miller, and Donald R. Sheehy
Discrete Comput Geom, 52(3): 476-491. 2014

We describe a new algorithm for computing the Voronoi diagram of a set of $n$ points in constant-dimensional Euclidean space. The running time of our algorithm is $O(f \log n \log \Delta)$ where $f$ is the output complexity of the Voronoi diagram and $\Delta$ is the spread of the input, the ratio of largest to smallest pairwise distances. Despite the simplicity of the algorithm and its analysis, it improves on the state of the art for all inputs with polynomial spread and near-linear output size. The key idea is to first build the Voronoi diagram of a superset of the input points using ideas from Voronoi refinement mesh generation. Then, the extra points are removed in a straightforward way that allows the total work to be bounded in terms of the output complexity, yielding the output sensitive bound. The removal only involves local flips and is inspired by kinetic data structures.

@inproceedings{miller14new,
Title = {A New Approach to Output-Sensitive Voronoi Diagrams and Delaunay Triangulations},
Author = {Gary L. Miller and Donald R. Sheehy},
Journal = {Discrete \& Computational Geometry},
Volume = {52},
Number = {3},
Pages = {476--491},
Year = {2014}}
Geometric Separators and the Parabolic Lift
Donald R. Sheehy
CCCG: The Canadian Conference in Computational Geometry 2013

A geometric separator for a set $U$ of $n$ geometric objects (usually balls) is a small (sublinear in $n$) subset whose removal disconnects the intersection graph of $U$ into roughly equal sized parts. These separators provide a natural way to do divide and conquer in geometric settings. A particularly nice geometric separator algorithm originally introduced by Miller and Thurston has three steps: compute a centerpoint in a space of one dimension higher than the input, compute a conformal transformation that centers'' the centerpoint, and finally, use the computed transformation to sample a sphere in the original space. The output separator is the subset of $S$ intersecting this sphere. It is both simple and elegant. We show that a change of perspective (literally) can make this algorithm even simpler by eliminating the entire middle step. By computing the centerpoint of the points lifted onto a paraboloid rather than using the stereographic map as in the original method, one can sample the desired sphere directly, without computing the conformal transformation.

@inproceedings{sheehy13geometric,
Title = {Geometric Separators and the Parabolic Lift},
Author = {Donald R. Sheehy},
Booktitle = {Canadian Conference in Computational Geometry},
Year = {2013}}
A New Approach to Output-Sensitive Voronoi Diagrams and Delaunay Triangulations
Gary L. Miller, and Donald R. Sheehy
SOCG: ACM Symposium on Computational Geometry 2013

We describe a new algorithm for computing the Voronoi diagram of a set of $n$ points in constant-dimensional Euclidean space. The running time of our algorithm is $O(f \log n \log \Delta)$ where $f$ is the output complexity of the Voronoi diagram and $\Delta$ is the spread of the input, the ratio of largest to smallest pairwise distances. Despite the simplicity of the algorithm and its analysis, it improves on the state of the art for all inputs with polynomial spread and near-linear output size. The key idea is to first build the Voronoi diagram of a superset of the input points using ideas from Voronoi refinement mesh generation. Then, the extra points are removed in a straightforward way that allows the total work to be bounded in terms of the output complexity, yielding the output sensitive bound. The removal only involves local flips and is inspired by kinetic data structures.

@inproceedings{miller13new,
Title = {A New Approach to Output-Sensitive Voronoi Diagrams and Delaunay Triangulations},
Author = {Gary L. Miller and Donald R. Sheehy},
Booktitle = {Proceedings of the 29th annual Symposium on Computational Geometry},
Pages = {281--288},
Year = {2013}}
A Fast Algorithm for Well-Spaced Points and Approximate Delaunay Graphs
Gary L. Miller, Donald R. Sheehy, and Ameya Velingker
SOCG: ACM Symposium on Computational Geometry 2013

We present a new algorithm that produces a well-spaced superset of points conforming to a given input set in any dimension with guaranteed optimal output size. We also provide an approximate Delaunay graph on the output points. Our algorithm runs in expected time $O(2^{O(d)}(n\log n + m))$, where $n$ is the input size, $m$ is the output point set size, and $d$ is the ambient dimension. The constants only depend on the desired element quality bounds.

To gain this new efficiency, the algorithm approximately maintains the Voronoi diagram of the current set of points by storing a superset of the Delaunay neighbors of each point. By retaining quality of the Voronoi diagram and avoiding the storage of the full Voronoi diagram, a simple exponential dependence on $d$ is obtained in the running time. Thus, if one only wants the approximate neighbors structure of a refined Delaunay mesh conforming to a set of input points, the algorithm will return a size $2^{O(d)}m$ graph in $2^{O(d)}(n\log n + m)$ expected time. If $m$ is superlinear in $n$, then we can produce a hierarchically well-spaced superset of size $2^{O(d)}n$ in $2^{O(d)}n\log n$ expected time.

@inproceedings{miller13fast,
Title = {A Fast Algorithm for Well-Spaced Points and Approximate Delaunay Graphs},
Author = {Gary L. Miller and Donald R. Sheehy and Ameya Velingker},
Booktitle = {Proceedings of the 29th annual Symposium on Computational Geometry},
Pages = {289--298},
Year = {2013}}
Linear-Size Approximations to the Vietoris-Rips Filtration
Donald R. Sheehy
Discrete Comput Geom, 49(4): 778-796 2013
Previously appeared in SOCG 2012

The Vietoris-Rips filtration is a versatile tool in topological data analysis. Unfortunately, it is often too large to construct in full. We show how to construct an $O(n)$-size filtered simplicial complex on an $n$-point metric space such that the persistence diagram is a good approximation to that of the Vietoris-Rips filtration. The filtration can be constructed in $O(n\log n)$ time. The constants depend only on the doubling dimension of the metric space and the desired tightness of the approximation. For the first time, this makes it computationally tractable to approximate the persistence diagram of the Vietoris-Rips filtration across all scales for large data sets.

Our approach uses a hierarchical net-tree to sparsify the filtration. We can either sparsify the data by throwing out points at larger scales to give a zigzag filtration, or sparsify the underlying graph by throwing out edges at larger scales to give a standard filtration. Both methods yield the same guarantees.

@article{sheehy13linear,
Title = {Linear-Size Approximations to the {V}ietoris-{R}ips Filtration},
Author = {Donald R. Sheehy},
Journal = {Discrete \& Computational Geometry},
Volume = {49},
Number = {4},
Pages = {778--796},
Year = {2013}}
A Multicover Nerve for Geometric Inference
Donald R. Sheehy
CCCG: The Canadian Conference in Computational Geometry 2012

We show that filtering the barycentric decomposition of a \v Cech complex by the cardinality of the vertices captures precisely the topology of $k$-covered regions among a collection of balls for all values of $k$. Moreover, we relate this result to the Vietoris-Rips complex to get an approximation in terms of the persistent homology.

@inproceedings{sheehy12multicover,
Title = {A Multicover Nerve for Geometric Inference},
Author = {Donald R. Sheehy},
Booktitle = {CCCG: Canadian Conference in Computational Geometry},
Year = {2012}}
New Bounds on the Size of Optimal Meshes
Donald R. Sheehy
Computer Graphics Forum, 31:5, 1627-1635 2012

The theory of optimal size meshes gives a method for analyzing the output size (number of simplices) of a Delaunay refinement mesh in terms of the integral of a sizing function over the input domain. The input points define a maximal such sizing function called the feature size. This paper presents a way to bound the feature size integral in terms of an easy to compute property of a suitable ordering of the point set. The key idea is to consider the pacing of an ordered point set, a measure of the rate of change in the feature size as points are added one at a time. In previous work, Miller et al.\ showed that if an ordered point set has pacing $\phi$, then the number of vertices in an optimal mesh will be $O(\phi^dn)$, where $d$ is the input dimension. We give a new analysis of this integral showing that the output size is only $\Theta(n + n\log \phi)$. The new analysis tightens bounds from several previous results and provides matching lower bounds. Moreover, it precisely characterizes inputs that yield outputs of size $O(n)$.

@article{sheehy12new,
Title = {{New Bounds on the Size of Optimal Meshes}},
Author = {Donald R. Sheehy},
Journal = {Computer Graphics Forum},
Volume= {31},
Number= {5},
Pages = {1627--1635},
Year = {2012}}
Minimax Rates for Homology Inference
Sivaraman Balakrishnan, Alessandro Rinaldo, Aarti Singh, Donald R. Sheehy, and Larry Wasserman
AISTATS: AI and Statistics 2012

Often, high dimensional data lie close to a low-dimensional submanifold and it is of interest to understand the geometry of these submanifolds. The homology groups of a manifold are important topological invariants that provide an algebraic summary of the manifold. These groups contain rich topological information, for instance, about the connected components, holes, tunnels and sometimes the dimension of the manifold. In this paper, we consider the statistical problem of estimating the homology of a manifold from noisy samples under several different noise models. We derive upper and lower bounds on the minimax risk for this problem. Our upper bounds are based on estimators which are constructed from a union of balls of appropriate radius around carefully selected points. In each case we establish complementary lower bounds using Le Cam's lemma.

@article{balakrishnan12minimax,
Title     = {Minimax rates for homology inference},
Author    = {Sivaraman Balakrishnan and
Alessandro Rinaldo and
Don Sheehy and
Aarti Singh and
Larry A. Wasserman},
Journal   = {Journal of Machine Learning Research - Proceedings Track},
Volume    = {22},
Pages     = {64--72},
Year      = {2012}}
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 27th 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

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}}
Approximate Centerpoints with Proofs
Gary L. Miller, and Donald R. Sheehy
Computational Geometry: Theory and Applications, 43(8): 647-654 2010
Previously appeared in SOCG 2009

We present the IteratedTverberg algorithm, the first deterministic algorithm for computing an approximate centerpoint of a set $S \subset R^d$ with running time subexponential in d. The algorithm is a derandomization of the IteratedRadon algorithm of Clarkson et al. (International Journal of Computational Geometry and Applications 6 (3) (1996) 357–377) and is guaranteed to terminate with an Ω(1/d2)-center. Moreover, it returns a polynomial-time checkable proof of the approximation guarantee, despite the coNP-completeness of testing centerpoints in general. We also explore the use of higher order Tverberg partitions to improve the running time of the deterministic algorithm and improve the approximation guarantee for the randomized algorithm. In particular, we show how to improve the $\Omega(1/d^2)$-center of the IteratedRadon algorithm to $\Omega(1/d^{\frac{r}{r-1}})$ for a cost of $O((rd)^d)$ in time for any integer r > 1.

@article{miller10approximate,
Title     = {Approximate centerpoints with proofs},
author    = {Gary L. Miller and Donald Sheehy},
journal   = {Computational Geometry: Theory and Applications},
volume    = {43},
number    = {8},
year      = {2010},
pages     = {647--654},
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

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

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

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

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

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

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

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