2026-10-01T11:19:59Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25888 2026-09-23T23:53:41Z ddc:004 open_access

Optimal-Cost Construction of Shallow Cuttings for 3-D Dominance Ranges in the I/O-Model Nekrich, Yakov Rahul, Saladi Data Structures I/O-efficient algorithms Orthogonal Range Searching 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₂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)), 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yakov Nekrich and Saladi Rahul 2026 Is Part Of LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2026.81 urn:nbn:de:0030-drops-258884 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.81 eng https://creativecommons.org/licenses/by/4.0/legalcode