Search Results

Documents authored by Ghosh, Anirban

Document
DOI: 10.4230/LIPIcs.SoCG.2026.53
Constructing Doppelgängers of Greedy Geometric Spanners in Practice

Authors: Anirban Ghosh

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract
Greedy geometric spanners are considered to be the gold standard for their near-optimal guarantees in terms of sparsity and total weight. However, their inefficient construction poses significant challenges for large-scale geometric networks, especially for low values of stretch factors (< 2). We present Θ-Greedy, a simple and practical parallel algorithm engineered for constructing doppelgängers of greedy geometric spanners that empirically resemble the greedy spanners in key structural and performance metrics, including average degree, degree, and lightness. Unlike approximate greedy spanners, doppelgängers of greedy spanners are almost indistinguishable from the actual greedy spanners in practice. In our experiments, Θ-Greedy consistently produced greedy spanner doppelgängers across a broad range of synthetic and real-world datasets, offering the first practical alternative to the computationally intensive greedy spanners. Θ-Greedy can construct a 1.1-spanner on a 128K-element uniformly distributed point set in well under 5 minutes. In contrast, Bucketing, the most practical greedy spanner algorithm, takes around 3 hours. For million-sized point sets, Θ-Greedy can run to completion in a few hours, making it much faster than Bucketing, which takes days to finish. In extensive experiments on synthetic and real-world datasets, Θ-Greedy delivered speedups of up to 147x over Bucketing while preserving greedy-like sparsity and weight. For broader uses of the algorithm and reproducibility, we share our engineered C++ code.
Cite as

Anirban Ghosh. Constructing Doppelgängers of Greedy Geometric Spanners in Practice. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 53:1-53:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{ghosh:LIPIcs.SoCG.2026.53,
  author =	{Ghosh, Anirban},
  title =	{{Constructing Doppelg\"{a}ngers of Greedy Geometric Spanners in Practice}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{53:1--53:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.53},
  URN =		{urn:nbn:de:0030-drops-258599},
  doi =		{10.4230/LIPIcs.SoCG.2026.53},
  annote =	{Keywords: geometric graph, geometric spanners, greedy spanners, algorithm engineering}
}
Document
Media Exposition
DOI: 10.4230/LIPIcs.SoCG.2022.68
Visualizing WSPDs and Their Applications (Media Exposition)

Authors: Anirban Ghosh, FNU Shariful, and David Wisnosky

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

Abstract
Introduced by Callahan and Kosaraju back in 1995, the concept of well-separated pair decomposition (WSPD) has occupied a special significance in computational geometry when it comes to solving distance problems in d-space. We present an in-browser tool that can be used to visualize WSPDs and several of their applications in 2-space. Apart from research, it can also be used by instructors for introducing WSPDs in a classroom setting. The tool will be permanently maintained by the third author at https://wisno33.github.io/VisualizingWSPDsAndTheirApplications/.
Cite as

Anirban Ghosh, FNU Shariful, and David Wisnosky. Visualizing WSPDs and Their Applications (Media Exposition). In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 68:1-68:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{ghosh_et_al:LIPIcs.SoCG.2022.68,
  author =	{Ghosh, Anirban and Shariful, FNU and Wisnosky, David},
  title =	{{Visualizing WSPDs and Their Applications}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{68:1--68:4},
  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.68},
  URN =		{urn:nbn:de:0030-drops-160760},
  doi =		{10.4230/LIPIcs.SoCG.2022.68},
  annote =	{Keywords: well-separated pair decomposition, nearest neighbor, geometric spanners, minimum spanning tree}
}
Document
Media Exposition
DOI: 10.4230/LIPIcs.SoCG.2021.61
An Interactive Tool for Experimenting with Bounded-Degree Plane Geometric Spanners (Media Exposition)

Authors: Fred Anderson, Anirban Ghosh, Matthew Graham, Lucas Mougeot, and David Wisnosky

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

Abstract
The construction of bounded-degree plane geometric spanners has been a focus of interest in the field of geometric spanners for a long time. To date, several algorithms have been designed with various trade-offs in degree and stretch factor. Using JSXGraph, a state-of-the-art JavaScript library for geometry, we have implemented seven of these sophisticated algorithms so that they can be used for further research and teaching computational geometry. We believe that our interactive tool can be used by researchers from related fields to understand and apply the algorithms in their research. Our tool can be run in any modern browser. The tool will be permanently maintained by the second author at https://ghoshanirban.github.io/bounded-degree-plane-spanners/index.html
Cite as

Fred Anderson, Anirban Ghosh, Matthew Graham, Lucas Mougeot, and David Wisnosky. An Interactive Tool for Experimenting with Bounded-Degree Plane Geometric Spanners (Media Exposition). In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 61:1-61:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{anderson_et_al:LIPIcs.SoCG.2021.61,
  author =	{Anderson, Fred and Ghosh, Anirban and Graham, Matthew and Mougeot, Lucas and Wisnosky, David},
  title =	{{An Interactive Tool for Experimenting with Bounded-Degree Plane Geometric Spanners}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{61:1--61:4},
  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.61},
  URN =		{urn:nbn:de:0030-drops-138607},
  doi =		{10.4230/LIPIcs.SoCG.2021.61},
  annote =	{Keywords: graph approximation, Delaunay triangulations, geometric spanners, plane spanners, bounded-degree spanners}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2020.57
Sparse Hop Spanners for Unit Disk Graphs

Authors: Adrian Dumitrescu, Anirban Ghosh, and Csaba D. Tóth

Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)

Abstract
A unit disk graph G on a given set of points P in the plane is a geometric graph where an edge exists between two points p,q ∈ P if and only if |pq| ≤ 1. A subgraph G' of G is a k-hop spanner if and only if for every edge pq ∈ G, the topological shortest path between p,q in G' has at most k edges. We obtain the following results for unit disk graphs. 1) Every n-vertex unit disk graph has a 5-hop spanner with at most 5.5n edges. We analyze the family of spanners constructed by Biniaz (2020) and improve the upper bound on the number of edges from 9n to 5.5n. 2) Using a new construction, we show that every n-vertex unit disk graph has a 3-hop spanner with at most 11n edges. 3) Every n-vertex unit disk graph has a 2-hop spanner with O(nlog n) edges. This is the first nontrivial construction of 2-hop spanners. 4) For every sufficiently large n, there exists a set P of n points on a circle, such that every plane hop spanner on P has hop stretch factor at least 4. Previously, no lower bound greater than 2 was known. 5) For every point set on a circle, there exists a plane 4-hop spanner. As such, this provides a tight bound for points on a circle. 6) The maximum degree of k-hop spanners cannot be bounded from above by a function of k.
Cite as

Adrian Dumitrescu, Anirban Ghosh, and Csaba D. Tóth. Sparse Hop Spanners for Unit Disk Graphs. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 57:1-57:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{dumitrescu_et_al:LIPIcs.ISAAC.2020.57,
  author =	{Dumitrescu, Adrian and Ghosh, Anirban and T\'{o}th, Csaba D.},
  title =	{{Sparse Hop Spanners for Unit Disk Graphs}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{57:1--57:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-173-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{181},
  editor =	{Cao, Yixin and Cheng, Siu-Wing and Li, Minming},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.57},
  URN =		{urn:nbn:de:0030-drops-134018},
  doi =		{10.4230/LIPIcs.ISAAC.2020.57},
  annote =	{Keywords: graph approximation, \epsilon-net, hop-spanner, unit disk graph, lower bound}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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