Search Results

Documents authored by Sheehy, Donald

Found 2 Possible Name Variants:

Sheehy, Donald R.

Document
Media Exposition
DOI: 10.4230/LIPIcs.SoCG.2023.64
Greedy Permutations and Finite Voronoi Diagrams (Media Exposition)

Authors: Oliver A. Chubet, Paul Macnichol, Parth Parikh, Donald R. Sheehy, and Siddharth S. Sheth

Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)

Abstract
We illustrate the computation of a greedy permutation using finite Voronoi diagrams. We describe the neighbor graph, which is a sparse graph data structure that facilitates efficient point location to insert a new Voronoi cell. This data structure is not dependent on a Euclidean metric space. The greedy permutation is computed in O(nlog Δ) time for low-dimensional data using this method [Sariel Har-Peled and Manor Mendel, 2006; Donald R. Sheehy, 2020].
Cite as

Oliver A. Chubet, Paul Macnichol, Parth Parikh, Donald R. Sheehy, and Siddharth S. Sheth. Greedy Permutations and Finite Voronoi Diagrams (Media Exposition). In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 64:1-64:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{chubet_et_al:LIPIcs.SoCG.2023.64,
  author =	{Chubet, Oliver A. and Macnichol, Paul and Parikh, Parth and Sheehy, Donald R. and Sheth, Siddharth S.},
  title =	{{Greedy Permutations and Finite Voronoi Diagrams}},
  booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
  pages =	{64:1--64:5},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-273-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{258},
  editor =	{Chambers, Erin W. and Gudmundsson, Joachim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.64},
  URN =		{urn:nbn:de:0030-drops-179146},
  doi =		{10.4230/LIPIcs.SoCG.2023.64},
  annote =	{Keywords: greedy permutation, Voronoi diagrams}
}
Document
Media Exposition
DOI: 10.4230/LIPIcs.SoCG.2023.65
The Sum of Squares in Polycubes (Media Exposition)

Authors: Donald R. Sheehy

Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)

Abstract
We give several ways to derive and express classic summation problems in terms of polycubes. We visualize them with 3D printed models. The video is here: http://go.ncsu.edu/sum_of_squares.
Cite as

Donald R. Sheehy. The Sum of Squares in Polycubes (Media Exposition). In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 65:1-65:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{sheehy:LIPIcs.SoCG.2023.65,
  author =	{Sheehy, Donald R.},
  title =	{{The Sum of Squares in Polycubes}},
  booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
  pages =	{65:1--65:6},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-273-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{258},
  editor =	{Chambers, Erin W. and Gudmundsson, Joachim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.65},
  URN =		{urn:nbn:de:0030-drops-179152},
  doi =		{10.4230/LIPIcs.SoCG.2023.65},
  annote =	{Keywords: Archimedes, polycubes, sum of squares}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2022.60
Nearly-Doubling Spaces of Persistence Diagrams

Authors: Donald R. Sheehy and Siddharth S. Sheth

Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)

Abstract
The space of persistence diagrams under bottleneck distance is known to have infinite doubling dimension. Because many metric search algorithms and data structures have bounds that depend on the dimension of the search space, the high-dimensionality makes it difficult to analyze and compare asymptotic running times of metric search algorithms on this space. We introduce the notion of nearly-doubling metrics, those that are Gromov-Hausdorff close to metric spaces of bounded doubling dimension and prove that bounded k-point persistence diagrams are nearly-doubling. This allows us to prove that in some ways, persistence diagrams can be expected to behave like a doubling metric space. We prove our results in great generality, studying a large class of quotient metrics (of which the persistence plane is just one example). We also prove bounds on the dimension of the k-point bottleneck space over such metrics. The notion of being nearly-doubling in this Gromov-Hausdorff sense is likely of more general interest. Some algorithms that have a dependence on the dimension can be analyzed in terms of the dimension of the nearby metric rather than that of the metric itself. We give a specific example of this phenomenon by analyzing an algorithm to compute metric nets, a useful operation on persistence diagrams.
Cite as

Donald R. Sheehy and Siddharth S. Sheth. Nearly-Doubling Spaces of Persistence Diagrams. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 60:1-60:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{sheehy_et_al:LIPIcs.SoCG.2022.60,
  author =	{Sheehy, Donald R. and Sheth, Siddharth S.},
  title =	{{Nearly-Doubling Spaces of Persistence Diagrams}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{60:1--60:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-227-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{224},
  editor =	{Goaoc, Xavier and Kerber, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.60},
  URN =		{urn:nbn:de:0030-drops-160686},
  doi =		{10.4230/LIPIcs.SoCG.2022.60},
  annote =	{Keywords: Topological Data Analysis, Persistence Diagrams, Gromov-Hausdorff Distance}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2021.57
Sketching Persistence Diagrams

Authors: Donald R. Sheehy and Siddharth Sheth

Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)

Abstract
Given a persistence diagram with n points, we give an algorithm that produces a sequence of n persistence diagrams converging in bottleneck distance to the input diagram, the ith of which has i distinct (weighted) points and is a 2-approximation to the closest persistence diagram with that many distinct points. For each approximation, we precompute the optimal matching between the ith and the (i+1)st. Perhaps surprisingly, the entire sequence of diagrams as well as the sequence of matchings can be represented in O(n) space. The main approach is to use a variation of the greedy permutation of the persistence diagram to give good Hausdorff approximations and assign weights to these subsets. We give a new algorithm to efficiently compute this permutation, despite the high implicit dimension of points in a persistence diagram due to the effect of the diagonal. The sketches are also structured to permit fast (linear time) approximations to the Hausdorff distance between diagrams - a lower bound on the bottleneck distance. For approximating the bottleneck distance, sketches can also be used to compute a linear-size neighborhood graph directly, obviating the need for geometric data structures used in state-of-the-art methods for bottleneck computation.
Cite as

Donald R. Sheehy and Siddharth Sheth. Sketching Persistence Diagrams. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 57:1-57:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{sheehy_et_al:LIPIcs.SoCG.2021.57,
  author =	{Sheehy, Donald R. and Sheth, Siddharth},
  title =	{{Sketching Persistence Diagrams}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{57:1--57:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-184-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{189},
  editor =	{Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.57},
  URN =		{urn:nbn:de:0030-drops-138569},
  doi =		{10.4230/LIPIcs.SoCG.2021.57},
  annote =	{Keywords: Bottleneck Distance, Persistent Homology, Approximate Persistence Diagrams}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2021.58
A Sparse Delaunay Filtration

Authors: Donald R. Sheehy

Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)

Abstract
We show how a filtration of Delaunay complexes can be used to approximate the persistence diagram of the distance to a point set in ℝ^d. Whereas the full Delaunay complex can be used to compute this persistence diagram exactly, it may have size O(n^⌈d/2⌉). In contrast, our construction uses only O(n) simplices. The central idea is to connect Delaunay complexes on progressively denser subsamples by considering the flips in an incremental construction as simplices in d+1 dimensions. This approach leads to a very simple and straightforward proof of correctness in geometric terms, because the final filtration is dual to a (d+1)-dimensional Voronoi construction similar to the standard Delaunay filtration. We also, show how this complex can be efficiently constructed.
Cite as

Donald R. Sheehy. A Sparse Delaunay Filtration. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 58:1-58:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{sheehy:LIPIcs.SoCG.2021.58,
  author =	{Sheehy, Donald R.},
  title =	{{A Sparse Delaunay Filtration}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{58:1--58:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-184-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{189},
  editor =	{Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.58},
  URN =		{urn:nbn:de:0030-drops-138579},
  doi =		{10.4230/LIPIcs.SoCG.2021.58},
  annote =	{Keywords: Delaunay Triangulation, Persistent Homology, Sparse Filtrations}
}
Document
DOI: 10.4230/LIPIcs.SOCG.2015.23
Visualizing Sparse Filtrations

Authors: Nicholas J. Cavanna, Mahmoodreza Jahanseir, and Donald R. Sheehy

Published in: LIPIcs, Volume 34, 31st International Symposium on Computational Geometry (SoCG 2015)

Abstract
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.
Cite as

Nicholas J. Cavanna, Mahmoodreza Jahanseir, and Donald R. Sheehy. Visualizing Sparse Filtrations. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 23-25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{cavanna_et_al:LIPIcs.SOCG.2015.23,
  author =	{Cavanna, Nicholas J. and Jahanseir, Mahmoodreza and Sheehy, Donald R.},
  title =	{{Visualizing Sparse Filtrations}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{23--25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-83-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{34},
  editor =	{Arge, Lars and Pach, J\'{a}nos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.23},
  URN =		{urn:nbn:de:0030-drops-50893},
  doi =		{10.4230/LIPIcs.SOCG.2015.23},
  annote =	{Keywords: Topological Data Analysis, Simplicial Complexes, Persistent Homology}
}

Sheehy, Donald

Document
DOI: 10.4230/LIPIcs.SoCG.2016.64
Interactive Geometric Algorithm Visualization in a Browser

Authors: Kirk Gardner, Lynn Asselin, and Donald Sheehy

Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)

Abstract
We present an online, interactive tool for writing and presenting interactive geometry demos suitable for classroom demonstrations. Code for the demonstrations is written in JavaScript using p5.js, a JavaScript library based on Processing.
Cite as

Kirk Gardner, Lynn Asselin, and Donald Sheehy. Interactive Geometric Algorithm Visualization in a Browser. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 64:1-64:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{gardner_et_al:LIPIcs.SoCG.2016.64,
  author =	{Gardner, Kirk and Asselin, Lynn and Sheehy, Donald},
  title =	{{Interactive Geometric Algorithm Visualization in a Browser}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{64:1--64:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-009-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{51},
  editor =	{Fekete, S\'{a}ndor and Lubiw, Anna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.64},
  URN =		{urn:nbn:de:0030-drops-59563},
  doi =		{10.4230/LIPIcs.SoCG.2016.64},
  annote =	{Keywords: Computational Geometry, Processing, JavaScript, Visualisation, Incremental Algorithms}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2016.69
Exploring Circle Packing Algorithms

Authors: Kevin Pratt, Connor Riley, and Donald Sheehy

Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)

Abstract
We present an interactive tool for visualizing and experimenting with different circle packing algorithms.
Cite as

Kevin Pratt, Connor Riley, and Donald Sheehy. Exploring Circle Packing Algorithms. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 69:1-69:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{pratt_et_al:LIPIcs.SoCG.2016.69,
  author =	{Pratt, Kevin and Riley, Connor and Sheehy, Donald},
  title =	{{Exploring Circle Packing Algorithms}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{69:1--69:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-009-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{51},
  editor =	{Fekete, S\'{a}ndor and Lubiw, Anna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.69},
  URN =		{urn:nbn:de:0030-drops-59616},
  doi =		{10.4230/LIPIcs.SoCG.2016.69},
  annote =	{Keywords: Computational Geometry, Processing, Javascript, Visualization, Incremental Algorithms}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact