zbMATH — the first resource for mathematics

On dominance reporting in 3D. (English) Zbl 1158.68363
Halperin, Dan (ed.) et al., Algorithms – ESA 2008. 16th annual European symposium, Karlsruhe, Germany, September 15–17, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-87743-1/pbk). Lecture Notes in Computer Science 5193, 41-51 (2008).
Summary: In this paper, we study the 3D dominance reporting problem in different models of computations and offer optimal results in the pointer machine and the external memory models and a near optimal result in the RAM model; all our results consume linear space. We can answer queries in \(O(\log n + k)\) time on a pointer machine, with \(O(\log _{B } n + k/B)\) I/Os in the external memory model and in \(O((\log \log n)^{2} + \log \log U + k)\) time in the RAM model and in a \(U\times U\times U\) integer grid. These improve the results of various papers, such as Makris and Tsakalidis (IPL’98), Vengroff and Vitter (STOC’96) and Nekrich (SOCG’07). Here, \(n, k\) and \(B\) are the input, output and block size respectively. With a \(\log ^{3} n\) fold increase in the space complexity these can be turned into orthogonal range reporting algorithms with matching query times, improving the previous orthogonal range searching results in the pointer machine and RAM models. Using our 3D results as base cases, we can provide improved orthogonal range reporting algorithms in \(\mathbb R^{d }\), \(d \geq 4\). We use randomization only in the preprocessing part and our query bounds are all worst case.
For the entire collection see [Zbl 1149.68011].

68P10 Searching and sorting
68P05 Data structures
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
Full Text: DOI