Search Results

Documents authored by von der Heydt, Jean-Pierre

Document
DOI: 10.4230/LIPIcs.ESA.2026.22
Benchmarking and Engineering Data Structures for Spherical Range Queries

Authors: Thomas Bläsius, Jean-Pierre von der Heydt, Tobias Kempf, Dennis Kobert, and Nikolai Maas

Published in: LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026)

Abstract
Spherical range queries are a fundamental primitive for working with spatial data. Many spatial data structures have been developed to answer these queries, but choosing the optimal one for a specific application is a difficult task. This is because theoretical worst-case bounds are often overly pessimistic, and existing average-case analyses are rather restricted and hard to compare. We address this problem with two main contributions. First, we present a comprehensive evaluation of state-of-the-art spatial indices across a diverse set of benchmarks. This includes a new benchmark based on graph embeddings alongside multiple real-world datasets from the literature. Our benchmark covers instances scaling up to 10M points and ranging between 2 and 960 dimensions. Second, we introduce the Sorted-Projection Radius KD-tree (SPRK-tree), a high-performance KD-tree variant. The SPRK-tree combines aggressive subtree pruning via radius reduction, sorted projection-based leaf nodes, and careful implementation optimizations. It consistently achieves the fastest query times in almost all benchmarks, and ranks second in the few remaining cases.
Cite as

Thomas Bläsius, Jean-Pierre von der Heydt, Tobias Kempf, Dennis Kobert, and Nikolai Maas. Benchmarking and Engineering Data Structures for Spherical Range Queries. In 34th Annual European Symposium on Algorithms (ESA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 388, pp. 22:1-22:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{blasius_et_al:LIPIcs.ESA.2026.22,
  author =	{Bl\"{a}sius, Thomas and von der Heydt, Jean-Pierre and Kempf, Tobias and Kobert, Dennis and Maas, Nikolai},
  title =	{{Benchmarking and Engineering Data Structures for Spherical Range Queries}},
  booktitle =	{34th Annual European Symposium on Algorithms (ESA 2026)},
  pages =	{22:1--22:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-445-1},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{388},
  editor =	{Bille, Philip and Pettie, Seth and Storandt, Sabine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.22},
  URN =		{urn:nbn:de:0030-drops-271585},
  doi =		{10.4230/LIPIcs.ESA.2026.22},
  annote =	{Keywords: Spherical Range Queries, Fixed-Radius Nearest Neighbor Search, Spatial Indexing, KD-tree, Benchmarking, Graph Embedding, SPRK-Tree}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.21
Structure and Independence in Hyperbolic Uniform Disk Graphs

Authors: Thomas Bläsius, Jean-Pierre von der Heydt, Sándor Kisfaludi-Bak, Marcus Wilhelm, and Geert van Wordragen

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract
We consider intersection graphs of disks of radius r in the hyperbolic plane. Unlike the Euclidean setting, these graph classes are different for different values of r, where very small r corresponds to an almost-Euclidean setting and r ∈ Ω(log n) corresponds to a firmly hyperbolic setting. We observe that larger values of r create simpler graph classes, at least in terms of separators and the computational complexity of the Independent Set problem. First, we show that intersection graphs of disks of radius r in the hyperbolic plane can be separated with 𝒪((1+1/r)log n) cliques in a balanced manner. Our second structural insight concerns Delaunay complexes in the hyperbolic plane and may be of independent interest. We show that for any set S of n points with pairwise distance at least 2r in the hyperbolic plane, the corresponding Delaunay complex has outerplanarity 1+𝒪((log n)/r), which implies a similar bound on the balanced separators and treewidth of such Delaunay complexes. Using this outerplanarity (and treewidth) bound we prove that Independent Set can be solved in n^𝒪(1+(log n)/r) time. The algorithm is based on dynamic programming on some unknown sphere cut decomposition that is based on the solution. The resulting algorithm is a far-reaching generalization of a result of Kisfaludi-Bak (SODA 2020), and it is tight under the Exponential Time Hypothesis. In particular, Independent Set is polynomial-time solvable in the firmly hyperbolic setting of r ∈ Ω(log n). Finally, in the case when the disks have ply (depth) at most 𝓁, we give a PTAS for Maximum Independent Set that has only quasi-polynomial dependence on 1/ε and 𝓁. Our PTAS is a further generalization of our exact algorithm.
Cite as

Thomas Bläsius, Jean-Pierre von der Heydt, Sándor Kisfaludi-Bak, Marcus Wilhelm, and Geert van Wordragen. Structure and Independence in Hyperbolic Uniform Disk Graphs. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 21:1-21:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{blasius_et_al:LIPIcs.SoCG.2025.21,
  author =	{Bl\"{a}sius, Thomas and von der Heydt, Jean-Pierre and Kisfaludi-Bak, S\'{a}ndor and Wilhelm, Marcus and van Wordragen, Geert},
  title =	{{Structure and Independence in Hyperbolic Uniform Disk Graphs}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{21:1--21:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.21},
  URN =		{urn:nbn:de:0030-drops-231731},
  doi =		{10.4230/LIPIcs.SoCG.2025.21},
  annote =	{Keywords: hyperbolic geometry, unit disk graphs, independent set, treewidth}
}
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