Optimal-Cost Construction of Shallow Cuttings for 3-D Dominance Ranges in the I/O-Model
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866908905774252032 |
|---|---|
| author | Nekrich, Yakov Rahul, Saladi |
| author_facet | Nekrich, Yakov Rahul, Saladi |
| contents | Shallow cuttings are a fundamental tool in computational geometry and spatial databases for solving offline and online range searching problems. For a set $P$ of $N$ points in 3-D, at SODA'14, Afshani and Tsakalidis designed an optimal $O(N\log_2N)$ time algorithm that constructs shallow cuttings for 3-D dominance ranges in internal memory. Even though shallow cuttings are used in the I/O-model to design space and query efficient range searching data structures, an efficient construction of them is not known till now. In this paper, we design an optimal-cost algorithm to construct shallow cuttings for 3-D dominance ranges. The number of I/Os performed by the algorithm is $O\left(\frac{N}{B}\log_{M/B}\left(\frac{N}{B}\right) \right)$, where $B$ is the block size and $M$ is the memory size.
As two applications of the optimal-cost construction algorithm, we design fast algorithms for offline 3-D dominance reporting and offline 3-D approximate dominance counting. We believe that our algorithm will find further applications in offline 3-D range searching problems and in improving construction cost of data structures for 3-D range searching problems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_21337 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Optimal-Cost Construction of Shallow Cuttings for 3-D Dominance Ranges in the I/O-Model Nekrich, Yakov Rahul, Saladi Computational Geometry Data Structures and Algorithms Shallow cuttings are a fundamental tool in computational geometry and spatial databases for solving offline and online range searching problems. For a set $P$ of $N$ points in 3-D, at SODA'14, Afshani and Tsakalidis designed an optimal $O(N\log_2N)$ time algorithm that constructs shallow cuttings for 3-D dominance ranges in internal memory. Even though shallow cuttings are used in the I/O-model to design space and query efficient range searching data structures, an efficient construction of them is not known till now. In this paper, we design an optimal-cost algorithm to construct shallow cuttings for 3-D dominance ranges. The number of I/Os performed by the algorithm is $O\left(\frac{N}{B}\log_{M/B}\left(\frac{N}{B}\right) \right)$, where $B$ is the block size and $M$ is the memory size. As two applications of the optimal-cost construction algorithm, we design fast algorithms for offline 3-D dominance reporting and offline 3-D approximate dominance counting. We believe that our algorithm will find further applications in offline 3-D range searching problems and in improving construction cost of data structures for 3-D range searching problems. |
| title | Optimal-Cost Construction of Shallow Cuttings for 3-D Dominance Ranges in the I/O-Model |
| topic | Computational Geometry Data Structures and Algorithms |
| url | https://arxiv.org/abs/2603.21337 |