2 Search Results for "Bouts, Quirijn W."

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

DOI: 10.4230/LIPIcs.ESA.2016.22

Mapping Polygons to the Grid with Small Hausdorff and Fréchet Distance

Authors: Quirijn W. Bouts, Irina Irina Kostitsyna, Marc van Kreveld, Wouter Meulemans, Willem Sonke, and Kevin Verbeek

Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)

Abstract

We show how to represent a simple polygon P by a (pixel-based) grid polygon Q that is simple and whose Hausdorff or Fréchet distance to P is small. For any simple polygon P, a grid polygon exists with constant Hausdorff distance between their boundaries and their interiors. Moreover, we show that with a realistic input assumption we can also realize constant Fréchet distance between the boundaries. We present algorithms accompanying these constructions, heuristics to improve their output while keeping the distance bounds, and experiments to assess the output.

Cite as

Quirijn W. Bouts, Irina Irina Kostitsyna, Marc van Kreveld, Wouter Meulemans, Willem Sonke, and Kevin Verbeek. Mapping Polygons to the Grid with Small Hausdorff and Fréchet Distance. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 22:1-22:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{bouts_et_al:LIPIcs.ESA.2016.22,
  author =	{Bouts, Quirijn W. and Irina Kostitsyna, Irina and van Kreveld, Marc and Meulemans, Wouter and Sonke, Willem and Verbeek, Kevin},
  title =	{{Mapping Polygons to the Grid with Small Hausdorff and Fr\'{e}chet Distance}},
  booktitle =	{24th Annual European Symposium on Algorithms (ESA 2016)},
  pages =	{22:1--22:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-015-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{57},
  editor =	{Sankowski, Piotr and Zaroliagis, Christos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.22},
  URN =		{urn:nbn:de:0030-drops-63738},
  doi =		{10.4230/LIPIcs.ESA.2016.22},
  annote =	{Keywords: grid mapping, Hausdorff distance, Fr\'{e}chet distance, digital geometry}
}

Refine by Type
2 Document/PDF
1 Document/HTML

Refine by Publication Year
1 2026
1 2016

Refine by Author
1 Bouts, Quirijn W.
1 Ghosh, Anirban
1 Irina Kostitsyna, Irina
1 Meulemans, Wouter
1 Sonke, Willem
Show More...

Refine by Series/Journal
2 LIPIcs

Refine by Classification
1 Theory of computation → Computational geometry

Refine by Keyword
1 Fréchet distance
1 Hausdorff distance
1 algorithm engineering
1 digital geometry
1 geometric graph
Show More...

2 Search Results for "Bouts, Quirijn W."

Constructing Doppelgängers of Greedy Geometric Spanners in Practice

Abstract

Cite as

Mapping Polygons to the Grid with Small Hausdorff and Fréchet Distance

Abstract

Cite as

Thanks for your feedback!

Could not send message