2 Search Results for "Sheth, Siddharth S."

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-dev.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
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-dev.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}
}
  • Refine by Author
  • 2 Sheehy, Donald R.
  • 2 Sheth, Siddharth S.
  • 1 Chubet, Oliver A.
  • 1 Macnichol, Paul
  • 1 Parikh, Parth

  • Refine by Classification
  • 2 Theory of computation → Computational geometry

  • Refine by Keyword
  • 1 Gromov-Hausdorff Distance
  • 1 Persistence Diagrams
  • 1 Topological Data Analysis
  • 1 Voronoi diagrams
  • 1 greedy permutation

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2022
  • 1 2023

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 Imprint Privacy Contact