2 Search Results for "Mendel, Manor"

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.2021.43
Reliable Spanners for Metric Spaces

Authors: Sariel Har-Peled, Manor Mendel, and Dániel Oláh

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

Abstract
A spanner is reliable if it can withstand large, catastrophic failures in the network. More precisely, any failure of some nodes can only cause a small damage in the remaining graph in terms of the dilation, that is, the spanner property is maintained for almost all nodes in the residual graph. Constructions of reliable spanners of near linear size are known in the low-dimensional Euclidean settings. Here, we present new constructions of reliable spanners for planar graphs, trees and (general) metric spaces.
Cite as

Sariel Har-Peled, Manor Mendel, and Dániel Oláh. Reliable Spanners for Metric Spaces. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 43:1-43:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{harpeled_et_al:LIPIcs.SoCG.2021.43,
  author =	{Har-Peled, Sariel and Mendel, Manor and Ol\'{a}h, D\'{a}niel},
  title =	{{Reliable Spanners for Metric Spaces}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{43:1--43:13},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.43},
  URN =		{urn:nbn:de:0030-drops-138423},
  doi =		{10.4230/LIPIcs.SoCG.2021.43},
  annote =	{Keywords: Spanners, reliability}
}
  • Refine by Author
  • 1 Chubet, Oliver A.
  • 1 Har-Peled, Sariel
  • 1 Macnichol, Paul
  • 1 Mendel, Manor
  • 1 Oláh, Dániel
  • Show More...

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

  • Refine by Keyword
  • 1 Spanners
  • 1 Voronoi diagrams
  • 1 greedy permutation
  • 1 reliability

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2021
  • 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