Simpler is Faster: Practical Distance Reporting by Sorting Along a Space-Filling Curve
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866912747547000832 |
|---|---|
| author | de Berg, Sarita Gæde, Emil Toftegaard van der Hoog, Ivor Reinstädtler, Henrik Rotenberg, Eva |
| author_facet | de Berg, Sarita Gæde, Emil Toftegaard van der Hoog, Ivor Reinstädtler, Henrik Rotenberg, Eva |
| contents | Range reporting is a classical problem in computational geometry. A (rectangular) reporting data structure stores a point set $P$, such that, given a (rectangular) query region $Δ$, it returns all points in $P \cap Δ$. A variety of data structures support such queries with differing asymptotic guarantees such as k-d trees, range trees, R-trees, and quadtrees. A common variant of range queries are distance reporting queries, where the input is a query point $q$ and a radius $δ$, and the goal is to report all points in $P$ within distance $δ$ of $q$. Such queries frequently arise as subroutines in geometric data structures. Practical implementations typically answer distance queries through rectangular range queries using the data structures listed before.
This paper revisits a simple and practical heuristic for distance reporting, originally proposed in TCS'97: sort the input point set~$P$ along a space-filling curve. Queries then reduce to scanning at most four contiguous ranges along the sorted curve. The fact that sorting along a space-filling curve is beneficial for range reporting is well-known. Many implementations use this technique to speed up their query and construction times. The point that this paper makes is subtle, but interesting: we argue that often, it is the space-filling curve rather than the overall data structure that provides the performance benefits. Thus, we offer a simple but effective alternative: only sort $P$ along a space-filling curve instead.
We compare this approach to eight range searching implementations, across an elaborate test suite of real-world and synthetic data. Our experiments confirm this simple 200-line code approach out-performs all high-end implementations in terms of space usage and construction time. It presents almost always the best query times. In a dynamic setting, our approach dominates in performance. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_19891 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Simpler is Faster: Practical Distance Reporting by Sorting Along a Space-Filling Curve de Berg, Sarita Gæde, Emil Toftegaard van der Hoog, Ivor Reinstädtler, Henrik Rotenberg, Eva Computational Geometry Range reporting is a classical problem in computational geometry. A (rectangular) reporting data structure stores a point set $P$, such that, given a (rectangular) query region $Δ$, it returns all points in $P \cap Δ$. A variety of data structures support such queries with differing asymptotic guarantees such as k-d trees, range trees, R-trees, and quadtrees. A common variant of range queries are distance reporting queries, where the input is a query point $q$ and a radius $δ$, and the goal is to report all points in $P$ within distance $δ$ of $q$. Such queries frequently arise as subroutines in geometric data structures. Practical implementations typically answer distance queries through rectangular range queries using the data structures listed before. This paper revisits a simple and practical heuristic for distance reporting, originally proposed in TCS'97: sort the input point set~$P$ along a space-filling curve. Queries then reduce to scanning at most four contiguous ranges along the sorted curve. The fact that sorting along a space-filling curve is beneficial for range reporting is well-known. Many implementations use this technique to speed up their query and construction times. The point that this paper makes is subtle, but interesting: we argue that often, it is the space-filling curve rather than the overall data structure that provides the performance benefits. Thus, we offer a simple but effective alternative: only sort $P$ along a space-filling curve instead. We compare this approach to eight range searching implementations, across an elaborate test suite of real-world and synthetic data. Our experiments confirm this simple 200-line code approach out-performs all high-end implementations in terms of space usage and construction time. It presents almost always the best query times. In a dynamic setting, our approach dominates in performance. |
| title | Simpler is Faster: Practical Distance Reporting by Sorting Along a Space-Filling Curve |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2508.19891 |