Summary: In this work, we present a collection of new results on two fundamental problems in geometric data structures: orthogonal point location and rectangle stabbing.

–

Orthogonal point location. We give the first linear-space data structure that supports 3-d point location queries on \(n\) disjoint axis-aligned boxes with optimal \(O(\log n)\) query time in the (arithmetic) pointer machine model. This improves the previous \(O(\log^{3/2} n)\) bound by S. Rahul [in: Proceedings of the 26th annual ACM-SIAM symposium on discrete algorithms, SODA 2015. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 200–211 (2015; Zbl 1371.68299)]. We similarly obtain the first linear-space data structure in the I/O model with optimal query cost, and also the first linear-space data structure in the word RAM model with sub-logarithmic query time.

–

Rectangle stabbing. We give the first linear-space data structure that supports 3-d 4-sided and 5-sided rectangle stabbing queries in optimal \(O(\log_wn+k)\) time in the word RAM model. We similarly obtain the first optimal data structure for the closely related problem of 2-d top-\(k\) rectangle stabbing in the word RAM model, and also improved results for 3-d 6-sided rectangle stabbing.

For point location, our solution is simpler than previous methods, and is based on an interesting variant of the van Emde Boas recursion, applied in a round-robin fashion over the dimensions, combined with bit-packing techniques. For rectangle stabbing, our solution is a variant by S. Alstrup et al. [“New data structures for orthogonal range searching”, in: Proceedings of 41st annual IEEE symposium on foundations of computer science, FOCS’00. Los Alamitos, CA: IEEE Computer Science. 198–207 (2000; doi:10.1109/SFCS.2000.892088)] grid-based recursive technique, combined with a number of new ideas.
For the entire collection see [Zbl 1392.68012].