@article{he_sheehy_2024, title={Guest editorial: Special issue on the 33rd Canadian Conference on Computational Geometry (CCCG)}, volume={116}, ISSN={["1879-081X"]}, DOI={10.1016/j.comgeo.2023.102035}, journal={COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS}, author={He, Meng and Sheehy, Don}, year={2024}, month={Jan} }
 @article{cavanna_sheehy_2020, title={Adaptive Metrics for Adaptive Samples}, volume={13}, ISSN={["1999-4893"]}, url={https://doi.org/10.3390/a13080200}, DOI={10.3390/a13080200}, abstractNote={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 critical points theory of distance functions. This ultimately leads to an algorithm for homology inference from samples whose spacing depends on their distance to a discrete representation of the complement space.}, number={8}, journal={ALGORITHMS}, publisher={MDPI AG}, author={Cavanna, Nicholas J. and Sheehy, Donald R.}, year={2020}, month={Aug} }
 @article{conchuir_gardner_jordan_bray_anderson_johnston_swope_harrison_sheehy_peters_2020, title={Efficient Algorithm for the Topological Characterization of Worm-like and Branched Micelle Structures from Simulations}, volume={16}, ISSN={["1549-9626"]}, DOI={10.1021/acs.jctc.0c00311}, abstractNote={Many surfactant-based formulations are utilized in industry as they produce desirable viscoelastic properties at low concentrations. These properties are due to the presence of worm-like micelles (WLMs), and as a result, understanding the processes that lead to WLM formation is of significant interest. Various experimental techniques have been applied with some success to this problem but can encounter issues probing key microscopic characteristics or the specific regimes of interest. The complementary use of computer simulations could provide an alternate route to accessing their structural and dynamic behavior. However, few computational methods exist for measuring key characteristics of WLMs formed in particle simulations. Further, their mathematical formulations are challenged by WLMs with sharp curvature profiles or density fluctuations along the backbone. Here, we present a new topological algorithm for identifying and characterizing WLMs in particle simulations, which has desirable mathematical properties that address shortcomings in previous techniques. We apply the algorithm to the case of sodium dodecyl sulfate micelles to demonstrate how it can be used to construct a comprehensive topological characterization of the observed structures.}, number={7}, journal={JOURNAL OF CHEMICAL THEORY AND COMPUTATION}, author={Conchuir, Breanndan O. and Gardner, Kirk and Jordan, Kirk E. and Bray, David J. and Anderson, Richard L. and Johnston, Michael A. and Swope, William C. and Harrison, Alex and Sheehy, Donald R. and Peters, Thomas J.}, year={2020}, month={Jul}, pages={4588–4598} }
 @inproceedings{cavanna_kiselius_sheehy_2018, title={Computing the Shift-Invariant Bottleneck Distance for Persistence Diagrams}, booktitle={CCCG: The Canadian Conference in Computational Geometry}, author={Cavanna, Nicholas J. and Kiselius, Oliver and Sheehy, Donald R.}, year={2018} }
 @inbook{sheehy_2018, title={Fréchet-Stable Signatures Using Persistence Homology}, ISBN={9781611975031}, url={http://dx.doi.org/10.1137/1.9781611975031.71}, DOI={10.1137/1.9781611975031.71}, abstractNote={For a metric space Y, the Frechet distance is a metric on trajectories f, g : [0, 1] → Y that minimizes maxt∈[0,1] dY(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 → Y where X is some topological space that minimizes over homeomorphisms from X → 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.}, booktitle={Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms}, publisher={Society for Industrial and Applied Mathematics}, author={Sheehy, Donald R.}, year={2018}, month={Jan}, pages={1100–1108} }
 @inproceedings{duggirala_sheehy_2018, title={When Can We Treat Trajectories as Points?}, booktitle={CCCG: The Canadian Conference in Computational Geometry}, author={Duggirala, Parasara Sridhar and Sheehy, Donald R.}, year={2018} }
 @inproceedings{cavanna_khoury_sheehy_2017, title={Supporting Ruled Polygons}, booktitle={CCCG: The Canadian Conference in Computational Geometry}, author={Cavanna, Nicholas J. and Khoury, Marc and Sheehy, Donald R.}, year={2017} }
 @inproceedings{cavanna_gardner_sheehy_2017, title={When and Why the Topological Coverage Criterion Works}, ISBN={9781611974782}, url={http://dx.doi.org/10.1137/1.9781611974782.177}, DOI={10.1137/1.9781611974782.177}, abstractNote={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.}, booktitle={Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms}, publisher={Society for Industrial and Applied Mathematics}, author={Cavanna, Nicholas J. and Gardner, Kirk P. and Sheehy, Donald R.}, year={2017}, month={Jan} }
 @inproceedings{cavanna_sheehy_2016, title={Adaptive Metrics for Adaptive Samples}, booktitle={CCCG: The Canadian Conference in Computational Geometry}, author={Cavanna, Nicholas J. and Sheehy, Donald R.}, year={2016} }
 @article{buchet_chazal_oudot_sheehy_2016, title={Efficient and robust persistent homology for measures}, volume={58}, ISSN={0925-7721}, url={http://dx.doi.org/10.1016/j.comgeo.2016.07.001}, DOI={10.1016/j.comgeo.2016.07.001}, abstractNote={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.}, journal={Computational Geometry}, publisher={Elsevier BV}, author={Buchet, Mickaël and Chazal, Frédéric and Oudot, Steve Y. and Sheehy, Donald R.}, year={2016}, month={Oct}, pages={70–96} }
 @inproceedings{pratt_riley_sheehy_2016, title={Exploring Circle Packing Algorithms}, DOI={10.4230/LIPIcs.SoCG.2016.69}, abstractNote={We present an interactive tool for visualizing and experimenting with different circle packing algorithms.}, booktitle={SOCG: Symposium on Computational Geometry (Multimedia Session)}, author={Pratt, Kevin and Riley, Connor and Sheehy, Donald R.}, year={2016} }
 @inproceedings{asselin_gardner_sheehy_2016, title={Interactive Geometric Algorithm Visualization in a Browser}, booktitle={SOCG: Symposium on Computational Geometry (Multimedia Session)}, author={Asselin, Lynn and Gardner, Kirk and Sheehy, Donald R.}, year={2016} }
 @inproceedings{jahanseir_sheehy_2016, title={Transforming Hierarchical Trees on Metric Spaces}, booktitle={CCCG: The Canadian Conference in Computational Geometry,2016}, author={Jahanseir, Mahmoodreza and Sheehy, Donald R.}, year={2016} }
 @inproceedings{gardner_sheehy_2016, title={kth Nearest Neighbor Sampling in the Plane}, booktitle={CCCG: The Canadian Conference in Computational Geometry}, author={Gardner, Kirk and Sheehy, Donald R.}, year={2016} }
 @inproceedings{cavanna_jahanseir_sheehy_2015, title={A Geometric Perspective on Sparse Filtrations}, booktitle={CCCG: The Canadian Conference in Computational Geometry}, author={Cavanna, Nicholas J. and Jahanseir, Mahmoodreza and Sheehy, Donald R.}, year={2015} }
 @inproceedings{sheehy_2015, title={An Output-Sensitive Algorithm for Computing Weightedα-Complexes}, booktitle={CCCG: The Canadian Conference in Computational Geometry}, author={Sheehy, Donald R.}, year={2015} }
 @inbook{cohen_fasy_miller_nayyeri_sheehy_velingker_2015, title={Approximating Nearest Neighbor Distances}, ISBN={9783319218397 9783319218403}, ISSN={0302-9743 1611-3349}, url={http://dx.doi.org/10.1007/978-3-319-21840-3_17}, DOI={10.1007/978-3-319-21840-3_17}, abstractNote={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 $$(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.}, booktitle={Lecture Notes in Computer Science}, publisher={Springer International Publishing}, author={Cohen, Michael B. and Fasy, Brittany Terese and Miller, Gary L. and Nayyeri, Amir and Sheehy, Donald R. and Velingker, Ameya}, year={2015}, pages={200–211} }
 @inproceedings{kerber_sheehy_skraba_2015, title={Persistent Homology and Nested Dissection}, ISBN={9781611974331}, url={http://dx.doi.org/10.1137/1.9781611974331.ch86}, DOI={10.1137/1.9781611974331.ch86}, abstractNote={Previous chapter Next chapter Full AccessProceedings Proceedings of the 2016 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)Persistent Homology and Nested DissectionMichael Kerber, Donald R. Sheehy, and Primoz SkrabaMichael Kerber, Donald R. Sheehy, and Primoz Skrabapp.1234 - 1245Chapter DOI:https://doi.org/10.1137/1.9781611974331.ch86PDFBibTexSections ToolsAdd to favoritesExport CitationTrack CitationsEmail SectionsAboutAbstract 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. Previous chapter Next chapter RelatedDetails Published:2016eISBN:978-1-61197-433-1 https://doi.org/10.1137/1.9781611974331Book Series Name:ProceedingsBook Code:PRDA16Book Pages:viii + 2106}, booktitle={Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms}, publisher={Society for Industrial and Applied Mathematics}, author={Kerber, Michael and Sheehy, Donald R. and Skraba, Primoz}, year={2015}, month={Dec} }
 @inproceedings{cavanna_jahanseir_sheehy_2015, title={Visualizing Sparse Filtrations}, DOI={10.4230/LIPIcs.SOCG.2015.23}, abstractNote={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.}, booktitle={SOCG: Symposium on Computational Geometry (Multimedia Session)}, author={Cavanna, Visualizing Sparse Filtrations Nicholas J. and Jahanseir, Mahmoodreza and Sheehy, Donald R.}, year={2015} }
 @article{miller_sheehy_2014, title={A New Approach to Output-Sensitive Construction of Voronoi Diagrams and Delaunay Triangulations}, volume={52}, ISSN={0179-5376 1432-0444}, url={http://dx.doi.org/10.1007/s00454-014-9629-y}, DOI={10.1007/s00454-014-9629-y}, abstractNote={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 \varDelta )$$ where $$f$$ is the output complexity of the Voronoi diagram and $$\varDelta $$ 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.}, number={3}, journal={Discrete & Computational Geometry}, publisher={Springer Science and Business Media LLC}, author={Miller, Gary L. and Sheehy, Donald R.}, year={2014}, month={Sep}, pages={476–491} }
 @inproceedings{buchet_chazal_oudot_sheehy_2014, title={Efficient and Robust Persistent Homology for Measures}, ISBN={9781611973747 9781611973730}, url={http://dx.doi.org/10.1137/1.9781611973730.13}, DOI={10.1137/1.9781611973730.13}, abstractNote={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.}, booktitle={Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms}, publisher={Society for Industrial and Applied Mathematics}, author={Buchet, Mickaël and Chazal, Frédéric and Oudot, Steve Y. and Sheehy, Donald R.}, year={2014}, month={Dec} }
 @inproceedings{sheehy_2014, title={The Persistent Homology of Distance Functions under Random Projection}, DOI={10.1145/2582112.2582126}, abstractNote={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 kth nearest neighbor distances, for which k = 1 and all weights equal to zero gives the usual distance to P.}, booktitle={SOCG: Symposium on Computational Geometry}, author={Sheehy, Donald R.}, year={2014} }
 @article{oudot_sheehy_2014, title={Zigzag Zoology: Rips Zigzags for Homology Inference}, volume={15}, ISSN={1615-3375 1615-3383}, url={http://dx.doi.org/10.1007/s10208-014-9219-7}, DOI={10.1007/s10208-014-9219-7}, abstractNote={For $$n$$ 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 in $$n$$ , with a constant factor depending only (exponentially) on the intrinsic dimension of $$X$$ . 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 (nonzigzag) Rips filtration itself. Thus, Rips zigzags 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. In particular, we give methods for reversing arrows and removing spaces from a zigzag while controlling the changes occurring in its barcode. 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.}, number={5}, journal={Foundations of Computational Mathematics}, publisher={Springer Science and Business Media LLC}, author={Oudot, Steve Y. and Sheehy, Donald R.}, year={2014}, month={Sep}, pages={1151–1186} }
 @inproceedings{miller_sheehy_velingker_2013, title={A fast algorithm for well-spaced points and approximate delaunay graphs}, ISBN={9781450320313}, url={http://dx.doi.org/10.1145/2462356.2462404}, DOI={10.1145/2462356.2462404}, abstractNote={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(2O(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 2O(d)m graph in 2O(d)(n log n + m) expected time. If m is superlinear in n, then we can produce a hierarchically well-spaced superset of size 2O(d)n in 2O(d)n log n expected time.}, booktitle={Proceedings of the 29th annual symposium on Symposuim on computational geometry - SoCG '13}, publisher={ACM Press}, author={Miller, Gary L. and Sheehy, Donald R. and Velingker, Ameya}, year={2013} }
 @inproceedings{miller_sheehy_2013, title={A new approach to output-sensitive voronoi diagrams and delaunay triangulations}, ISBN={9781450320313}, url={http://dx.doi.org/10.1145/2462356.2462372}, DOI={10.1145/2462356.2462372}, abstractNote={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 Δ) where f is the output complexity of the Voronoi diagram and Δ 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.}, booktitle={Proceedings of the 29th annual symposium on Symposuim on computational geometry - SoCG '13}, publisher={ACM Press}, author={Miller, Gary L. and Sheehy, Donald R.}, year={2013} }
 @inproceedings{sheehy_2013, title={Geometric Separators and the Parabolic Lift}, booktitle={CCCG: The Canadian Conference in Computational Geometry}, author={Sheehy, Donald R.}, year={2013} }
 @article{sheehy_2013, title={Linear-Size Approximations to the Vietoris–Rips Filtration}, volume={49}, ISSN={0179-5376 1432-0444}, url={http://dx.doi.org/10.1007/s00454-013-9513-1}, DOI={10.1007/s00454-013-9513-1}, abstractNote={The Vietoris–Rips filtration is a versatile tool in topological data analysis. It is a sequence of simplicial complexes built on a metric space to add topological structure to an otherwise disconnected set of points. It is widely used because it encodes useful information about the topology of the underlying metric space. This information is often extracted from its so-called persistence diagram. Unfortunately, this filtration 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 its persistence diagram is a good approximation to that of the Vietoris–Rips filtration. This new filtration can be constructed in $$O(n\log n)$$ time. The constant factors in both the size and the running time 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. We describe two different sparse filtrations. The first is a zigzag filtration that removes points as the scale increases. The second is a (non-zigzag) filtration that yields the same persistence diagram. Both methods are based on a hierarchical net-tree and yield the same guarantees.}, number={4}, journal={Discrete & Computational Geometry}, publisher={Springer Science and Business Media LLC}, author={Sheehy, Donald R.}, year={2013}, month={May}, pages={778–796} }
 @inproceedings{oudot_sheehy_2013, title={Zigzag zoology}, ISBN={9781450320313}, url={http://dx.doi.org/10.1145/2462356.2462371}, DOI={10.1145/2462356.2462371}, abstractNote={For n\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$n$$\end{document} points sampled near a compact set X\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$X$$\end{document}, the persistence barcode of the Rips filtration built from the sample contains information about the homology of X\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$X$$\end{document} as long as X\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$X$$\end{document} satisfies some geometric assumptions. The Rips filtration is prohibitively large; however, zigzag persistence can be used to keep the size linear in n\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$n$$\end{document}, with a constant factor depending only (exponentially) on the intrinsic dimension of X\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$X$$\end{document}. 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 (nonzigzag) Rips filtration itself. Thus, Rips zigzags 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. In particular, we give methods for reversing arrows and removing spaces from a zigzag while controlling the changes occurring in its barcode. 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.}, booktitle={Proceedings of the 29th annual symposium on Symposuim on computational geometry - SoCG '13}, publisher={ACM Press}, author={Oudot, Steve Y. and Sheehy, Donald R.}, year={2013} }
 @inproceedings{sheehy_2012, title={A Multicover Nerve for Geometric Inference}, booktitle={CCCG: The Canadian Conference in Computational Geometry}, author={Sheehy, Donald R.}, year={2012} }
 @inproceedings{sheehy_2012, title={Linear-size approximations to the vietoris-rips filtration}, ISBN={9781450312998}, url={http://dx.doi.org/10.1145/2261250.2261286}, DOI={10.1145/2261250.2261286}, abstractNote={The Vietoris–Rips filtration is a versatile tool in topological data analysis. It is a sequence of simplicial complexes built on a metric space to add topological structure to an otherwise disconnected set of points. It is widely used because it encodes useful information about the topology of the underlying metric space. This information is often extracted from its so-called persistence diagram. Unfortunately, this filtration is often too large to construct in full. We show how to construct an O(n)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(n)$$\end{document}-size filtered simplicial complex on an n\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$n$$\end{document}-point metric space such that its persistence diagram is a good approximation to that of the Vietoris–Rips filtration. This new filtration can be constructed in O(nlogn)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(n\log n)$$\end{document} time. The constant factors in both the size and the running time 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. We describe two different sparse filtrations. The first is a zigzag filtration that removes points as the scale increases. The second is a (non-zigzag) filtration that yields the same persistence diagram. Both methods are based on a hierarchical net-tree and yield the same guarantees.}, booktitle={Proceedings of the 2012 symposuim on Computational Geometry - SoCG '12}, publisher={ACM Press}, author={Sheehy, Donald R.}, year={2012} }
 @inproceedings{balakrishnan_rinaldo_singh_sheehy_wasserman_2012, title={Minimax Rates for Homology Inference}, booktitle={AISTATS: AI and Statistics}, author={Balakrishnan, Sivaraman and Rinaldo, Alessandro and Singh, Aarti and Sheehy, Donald R. and Wasserman, Larry}, year={2012} }
 @article{sheehy_2012, title={New Bounds on the Size of Optimal Meshes}, volume={31}, ISSN={0167-7055}, url={http://dx.doi.org/10.1111/j.1467-8659.2012.03168.x}, DOI={10.1111/j.1467-8659.2012.03168.x}, abstractNote={Abstract}, number={5}, journal={Computer Graphics Forum}, publisher={Wiley}, author={Sheehy, Donald R.}, year={2012}, month={Aug}, pages={1627–1635} }
 @inproceedings{miller_phillips_sheehy_2011, title={Beating the spread}, ISBN={9781450306829}, url={http://dx.doi.org/10.1145/1998196.1998252}, DOI={10.1145/1998196.1998252}, abstractNote={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 O(n log n + m) time, 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. It can terminate early in O(n log n) time returning a O(n) size Voronoi diagram of a superset of P, 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. We reduce this dependence to O(log n) by using a sequence of ε-nets to determine input insertion order into a 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.}, booktitle={Proceedings of the 27th annual ACM symposium on Computational geometry - SoCG '11}, publisher={ACM Press}, author={Miller, Gary L. and Phillips, Todd and Sheehy, Donald R.}, year={2011} }
 @article{miller_sheehy_2010, title={Approximate centerpoints with proofs}, volume={43}, ISSN={0925-7721}, url={http://dx.doi.org/10.1016/j.comgeo.2010.04.006}, DOI={10.1016/j.comgeo.2010.04.006}, abstractNote={We present the IteratedTverberg algorithm, the first deterministic algorithm for computing an approximate centerpoint of a set S⊂Rd with running time sub-exponential 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 Ω(1/d2)-center of the IteratedRadon algorithm to Ω(1/drr−1) for a cost of O((rd)d) in time for any integer r>1.}, number={8}, journal={Computational Geometry}, publisher={Elsevier BV}, author={Miller, Gary L. and Sheehy, Donald R.}, year={2010}, month={Oct}, pages={647–654} }
 @inproceedings{hudson_miller_oudot_sheehy_2010, title={Topological inference via meshing}, ISBN={9781450300162}, url={http://dx.doi.org/10.1145/1810959.1811006}, DOI={10.1145/1810959.1811006}, abstractNote={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 ℜd. Classical approaches rely on the Cech, Rips, ±-complex, or witness complex filtrations of P, whose complexities scale up very badly with d. For instance, the ±-complex filtration incurs the n Ω(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 2O(d2)n. Our filtrations interleave multiplicatively with the family of offsets of P, so that the persistence diagram of P can be approximated in 2O(d2)n3 time in theory, with a near-linear observed running time in practice. Thus, our approach remains tractable in medium dimensions, say 4 to 10.}, booktitle={Proceedings of the 2010 annual symposium on Computational geometry - SoCG '10}, publisher={ACM Press}, author={Hudson, Benoit and Miller, Gary L. and Oudot, Steve Y. and Sheehy, Donald R.}, year={2010} }
 @inproceedings{miller_sheehy_2009, title={Approximate center points with proofs}, ISBN={9781605585017}, url={http://dx.doi.org/10.1145/1542362.1542395}, DOI={10.1145/1542362.1542395}, abstractNote={We present the Iterated-Tverberg algorithm, the first deterministic algorithm for computing an approximate centerpoint of a set S ∈ Rd 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/d2)-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/d2)-center of the Iterated-Radon algorithm to O(1/dr/(r-1)) for a cost of O((rd)d) in time for any integer r.}, booktitle={Proceedings of the 25th annual symposium on Computational geometry - SCG '09}, publisher={ACM Press}, author={Miller, Gary L. and Sheehy, Donald R.}, year={2009} }
 @inproceedings{hudson_miller_phillips_sheehy_2009, title={Size Complexity of Volume Meshes vs. Surface Meshes}, ISBN={9780898716801 9781611973068}, url={http://dx.doi.org/10.1137/1.9781611973068.113}, DOI={10.1137/1.9781611973068.113}, abstractNote={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 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.}, booktitle={Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms}, publisher={Society for Industrial and Applied Mathematics}, author={Hudson, Benoît and Miller, Gary L. and Phillips, Todd and Sheehy, Don}, year={2009}, month={Jan} }
 @inproceedings{miller_phillips_sheehy_2009, title={The Centervertex Theorem for Wedge Depth}, booktitle={CCCG: The Canadian Conference in Computational Geometry}, author={Miller, Gary L. and Phillips, Todd and Sheehy, Donald R.}, year={2009} }
 @inproceedings{derryberry_sleator_sheehy_woo_2008, title={Achieving Spatial Adaptivity while Finding Approximate Nearest Neighbors}, booktitle={CCCG: The Canadian Conference in Computational Geometry}, author={Derryberry, Jonathan and Sleator, Daniel D. and Sheehy, Donald R. and Woo, Maverick}, year={2008} }
 @inproceedings{miller_phillips_sheehy_2008, title={Linear-size meshes}, booktitle={CCCG: The Canadian Conference in Computational Geometry}, author={Miller, Gary L. and Phillips, Todd and Sheehy, Donald R.}, year={2008} }
 @article{danciger_devadoss_mugno_sheehy_ward_2008, title={Shape deformation in continuous map generalization}, volume={13}, ISSN={1384-6175 1573-7624}, url={http://dx.doi.org/10.1007/s10707-008-0049-0}, DOI={10.1007/s10707-008-0049-0}, number={2}, journal={GeoInformatica}, publisher={Springer Science and Business Media LLC}, author={Danciger, Jeff and Devadoss, Satyan L. and Mugno, John and Sheehy, Don and Ward, Rachel}, year={2008}, month={May}, pages={203–221} }
 @inbook{miller_phillips_sheehy_2007, title={Size Competitive Meshing Without Large Angles}, ISBN={9783540734192 9783540734208}, ISSN={0302-9743 1611-3349}, url={http://dx.doi.org/10.1007/978-3-540-73420-8_57}, DOI={10.1007/978-3-540-73420-8_57}, abstractNote={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°. 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.}, booktitle={Automata, Languages and Programming}, publisher={Springer Berlin Heidelberg}, author={Miller, Gary L. and Phillips, Todd and Sheehy, Donald}, year={2007}, month={Aug}, pages={655–666} }
 @article{danciger_devadoss_sheehy_2006, title={Compatible triangulations and point partitions by series-triangular graphs}, volume={34}, ISSN={0925-7721}, url={http://dx.doi.org/10.1016/j.comgeo.2005.11.003}, DOI={10.1016/j.comgeo.2005.11.003}, abstractNote={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.}, number={3}, journal={Computational Geometry}, publisher={Elsevier BV}, author={Danciger, Jeff and Devadoss, Satyan L. and Sheehy, Don}, year={2006}, month={Jul}, pages={195–202} }