Optimal-Cost Construction of Shallow Cuttings for 3-D Dominance Ranges in the I/O-Model

Yakov Nekrich, Saladi Rahul · 2026

Read Optimal-Cost Construction of Shallow Cuttings for 3-D Dominance Ranges in the I/O-Model by Yakov Nekrich, Saladi Rahul (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-21337.txt.

Introduction

Nekrich and Rahul design an optimal-cost algorithm to build shallow cuttings for 3-D dominance ranges in the I/O model. Shallow cuttings are a core tool for range searching in computational geometry and spatial databases. An optimal internal memory algorithm existed, but no efficient I/O construction was known. Their method performs a number of I/Os that matches the optimal bound, given block and memory sizes. As applications, they give fast algorithms for offline 3-D dominance reporting and approximate dominance counting.

Catalog record

CREATORYakov Nekrich, Saladi Rahul
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE63936
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.21337

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Optimal-Cost Construction of Shallow Cuttings for 3-D Dominance Ranges in the I/O-Model Yakov Nekrich, Saladi Rahul Abstract Shallow cuttings are a fundamental tool in computational geometry and spatial databases for solving offline and online range searching problems. For a set P P of N N points in 3-D, at SODA’14, Afshani and Tsakalidis designed an optimal O ⁡ ( N ​ log 2 ​ N ) O(N\log_{2}N) 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 ⁡ ( N B ​ log M / B ​ ( N B ) ) O\left(\frac{N}{B}\log_{M/B}\left(\frac{N}{B}\right)\right) , where B B is the block size and M 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. 1 Introduction Shallow cuttings are one of the most fundamental tools used for designing range searching data structures in computational geometry [ 5 , 1 , 2 , 3 , 14 ] and spatial databases [ 16 , 17 , 6 ] . The main contribution of this paper is the first known optimal-cost construction of shallow cuttings for 3-D dominance ranges in the I/O-model . As a consequence, we obtain efficient algorithms for the offline 3-D dominance reporting problem and the offline 3-D approximate counting problem. Shallow cuttings for 3-D dominance ranges. Consider two 3-D points p and q . A point p dominates another point q if and only if p has a higher coordinate value than q in each dimension. Let P be a set of N points in 3-D. A k -level shallow cutting of P [ 5 ] (See Figure 1 (a)) is a collection \mathcal{C} of cells of the form (-\infty,x]\times(-\infty,y]\times(-\infty,z] satisfying the following three properties: 1. The number of cells is O(n/k) , i.e., |\mathcal{C}|=O(n/k) . 2. Each cell in \mathcal{C} contains at most 10k points from P . 3. Any 3-D point that dominates at most k points of P lies inside at least one cell in \mathcal{C} . Figure 1 : (a) A schematic representation of a k -level 3-D shallow cutting, (b) 3-D dominance reporting and approximate counting query, (c) 3-D orthogonal range reporting query, (d) 3-D rectangle stabbing query. I/O-model of computation. We will construct shallow cuttings for 3-D dominance ranges in the I/O-model of computation [ 23 ] . In the era of big-data, it is natural that the input will not fit completely in the internal memory, and hence, resides in the hard-disk (or the external memory). In this model, the internal memory has M words, and the hard-disk has been formatted into blocks of B words. An I/O operation exchanges a block of data between the disk and the memory. The space of a data structure is the number of blocks occupied in the external memory, and the running time of an algorithm is the number of I/Os performed. The CPU calculation is free. A natural assumption is that M=\Omega(B) . 3-D orthogonal range searching. Orthogonal range searching and related problems are foundational problems on which the fields of computational geometry and spatial databases grew. Naturally, they have been well studied in the I/O-model of computation. Consider the following problems for which the state-of-the-art data structures in the I/O-model extensively rely on the clever use of shallow cuttings for 3-D dominance ranges: 1. In the 3-D orthogonal range reporting problem (Figure 1 (c)), the input is a set P of N points in 3-D. Preprocess P into a space-efficient data structure, so that given an axis-aligned query box q=[x_{1},x_{2}]\times[y_{1},y_{2}]\times[z_{1},z_{2}] , the goal is to quickly report P\cap q (the points of P lying inside q ). AT FOCS’09, Afshani, Arge, and Larsen [ 1 ] presented a data structure for this problem with space O\left(\frac{N}{B}\left(\frac{\log N}{\log\log_{B}N}\right)^{3}\right) and query I/Os O(\log_{B}N+k/B) , where k is the number of points reported. 2. The building block for the above problem is the 3-D dominance reporting problem (Figure 1 (b)), where the query is a 3-D dominance range q=(-\infty,x]\times(-\infty,y]\times(-\infty,z] . At ESA’08, Afshani [ 15 ] presented a data structure for this problem with space O(N/B) and query I/Os O(\log_{B}N+k/B) . This is optimal in terms of space and query I/Os. 3. At SoCG’09, Afshani, Hamilton, and Zeh presented a general approach to design data structures to answer the relative (1+\varepsilon) -approximate counting query for a general class of problems including the 3-D dominance setting. Here the goal is to output the estimate of |P\cap q| . An optimal solution in terms of space and query I/Os was obtained. 4. Rectangle stabbing reporting (Figure 1 (d)) is the “reverse” of orthogonal range reporting where the input is a set of axis-aligned 3-D boxes and the query is a 3-D point. Arguably, rectangle stabbing reporting is as important as orthogonal range reporting and is well studied in the literature. The current state-of-the-art results in internal memory models of computation for rectangle stabbing reporting by Rahul [ 18 ] at SODA’15 and Chan, Nekrich, Rahul, and Tsakalidis [ 9 ] at ICALP’18 rely on shallow cuttings for 3-D dominance ranges. It is unlikely that a linear-space data structure in the I/O-model can be constructed without using shallow cuttings. Lack of fast construction of data structures. An important criteria in the design of the data structures is to optimize the I/Os required to construct the data structure. A severe limitation of all the above solutions is the lack of such fast construction algorithms. In fact, quoting from one of the above papers (Afshani, Hamilton, and Zeh [ 3 ] ), “All data structures presented in this paper are static, and no efficient construction methods for these structures are known in the I/O or cache-oblivious model. The main obstacle is the lack of an I/O-efficient or cache-oblivious construction procedure for shallow cuttings.” We believe that our work on optimal-cost construction of shallow cuttings for 3-D dominance ranges will trigger further work to design fast construction of data structures for the above mentioned problems. Lack of optimal solutions for offline 3-D orthogonal range searching. In the offline orthogonal range searching problem, we are given a set Q of queries upfront along with the point set P . Many 2-D offline problems in computational geometry (including range searching type problems) have been optimally solved in the I/O-model. See the survey paper by Vitter (Theorem 8.1 in [ 23 ] provides a comprehensive list of more than ten problems in 2-D which are solved I/O-optimally). However, to the best of our knowledge, offline 3-D orthogonal range searching problems have not received the same attention in spite of their fundamental nature. Again, the lack of optimal-cost shallow cuttings in 3-D is

Read the complete text