Orthogonal range searching on the RAM, revisited.

*(English)*Zbl 1283.68139
Proceedings of the 27th annual symposium on computational geometry, SoCG 2011, Paris, France, June 13–15, 2011. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-0682-9). 1-10 (2011).

Summary: We present a number of new results on one of the most extensively studied topics in computational geometry, orthogonal range searching. All our results are in the standard word RAM model:

We present two data structures for 2-d orthogonal range emptiness. The first achieves \(O(n \lg \lg n)\) space and \(O(\lg \lg n)\) query time, assuming that the \(n\) given points are in rank space. This improves the previous results by S. Alstrup et al. [“New data structures for orthogonal range searching”, in: Proceedings of the 41st annual symposium on foundations of computer science, FOCS ’00. Washington, DC: IEEE Computer Society. 198–207 (2000)], with \(O(n \lg^{\epsilon}n)\) space and \(O(\lg \lg n)\) query time, or with \(O(n\lg\lg n)\) space and \(O(\lg^{2}\lg n)\) query time.

Our second data structure uses \(O(n)\) space and answers queries in \(O(\lg^{\epsilon} n)\) time. The best previous \(O(n)\)-space data structure, due to Y. Nekrich [Lect. Notes Comput. Sci. 4619, 15–26 (2007; Zbl 1209.68162)], answers queries in \(O(\lg n/\lg\lg n)\) time. We give a data structure for 3-d orthogonal range reporting with \(O(n \lg^{1+{\epsilon}} n)\) space and \(O(\lg\lg n + k)\) query time for points in rank space, for any constant \({\epsilon}>0\). This improves the previous results in [P. Afshani, Lect. Notes Comput. Sci. 5193, 41–51 (2008; Zbl 1158.68363); M. Karpinski and Y. Nekrich, Lect. Notes Comput. Sci. 5609, 215–224 (2009; Zbl 1248.68524); T. M. Chan, “Persistent predecessor search and orthogonal point location on the word RAM”, in: Proceedings of the twenty-second annual ACM-SIAM symposium on discrete algorithms, SODA ’11. New York, NY: ACM Press. 1131–1145 (2011)], with \(O(n \lg^{3} n)\) space and \(O(\lg\lg n + k)\) query time, or with \(O(n \lg^{1+\epsilon}n)\) space and \(O(\lg^{2}\lg n + k)\) query time. Consequently, we obtain improved upper bounds for orthogonal range reporting in all constant dimensions above 3.

Our approach also leads to a new data structure for 2D orthogonal range minimum queries with \(O(n\lg^{\epsilon} n)\) space and \(O(\lg \lg n)\) query time for points in rank space.

3. We give a randomized algorithm for 4-d offline dominance range reporting/emptiness with running time \(O(n \log n)\) plus the output size. This resolves two open problems (both appeared in F. P. Preparata and M. I. Shamos’s seminal book [Computational geometry. An introduction. New York etc.: Springer-Verlag (1985; Zbl 0575.68059; Zbl 0759.68037)]):

(a) Given a set of \(n\) axis-aligned rectangles in the plane, we can report all \(k\) enclosure pairs (i.e., pairs \((r_{1},r_{2})\) where rectangle \(r_{1}\) completely encloses rectangle \(r_{2}\)) in \(O(n \lg n + k)\) expected time;

(b) Given a set of \(n\) points in 4-d, we can find all maximal points (points not dominated by any other points) in \(O(n \lg n)\) expected time.

The most recent previous development on (a) was reported back in SoCG’95 by P. Gupta et al. [Int. J. Comput. Geom. Appl. 7, No. 5, 437–455 (1997; Zbl 0888.68066)], whose main result was an \(O([n \lg n + k] \lg \lg n)\) algorithm. The best previous result on (b) was an \(O(n \lg n \lg \lg n)\) algorithm due to H. N. Gabow [“Scaling and related techniques for geometry problems”, in: Proceedings of the sixteenth annual ACM symposium on theory of computing, STOC ’84. New York, NY: ACM Press. 135–143 (1984)]. As a consequence, we also obtain the current-record time bound for the maxima problem in all constant dimensions above.

For the entire collection see [Zbl 1271.68010].

We present two data structures for 2-d orthogonal range emptiness. The first achieves \(O(n \lg \lg n)\) space and \(O(\lg \lg n)\) query time, assuming that the \(n\) given points are in rank space. This improves the previous results by S. Alstrup et al. [“New data structures for orthogonal range searching”, in: Proceedings of the 41st annual symposium on foundations of computer science, FOCS ’00. Washington, DC: IEEE Computer Society. 198–207 (2000)], with \(O(n \lg^{\epsilon}n)\) space and \(O(\lg \lg n)\) query time, or with \(O(n\lg\lg n)\) space and \(O(\lg^{2}\lg n)\) query time.

Our second data structure uses \(O(n)\) space and answers queries in \(O(\lg^{\epsilon} n)\) time. The best previous \(O(n)\)-space data structure, due to Y. Nekrich [Lect. Notes Comput. Sci. 4619, 15–26 (2007; Zbl 1209.68162)], answers queries in \(O(\lg n/\lg\lg n)\) time. We give a data structure for 3-d orthogonal range reporting with \(O(n \lg^{1+{\epsilon}} n)\) space and \(O(\lg\lg n + k)\) query time for points in rank space, for any constant \({\epsilon}>0\). This improves the previous results in [P. Afshani, Lect. Notes Comput. Sci. 5193, 41–51 (2008; Zbl 1158.68363); M. Karpinski and Y. Nekrich, Lect. Notes Comput. Sci. 5609, 215–224 (2009; Zbl 1248.68524); T. M. Chan, “Persistent predecessor search and orthogonal point location on the word RAM”, in: Proceedings of the twenty-second annual ACM-SIAM symposium on discrete algorithms, SODA ’11. New York, NY: ACM Press. 1131–1145 (2011)], with \(O(n \lg^{3} n)\) space and \(O(\lg\lg n + k)\) query time, or with \(O(n \lg^{1+\epsilon}n)\) space and \(O(\lg^{2}\lg n + k)\) query time. Consequently, we obtain improved upper bounds for orthogonal range reporting in all constant dimensions above 3.

Our approach also leads to a new data structure for 2D orthogonal range minimum queries with \(O(n\lg^{\epsilon} n)\) space and \(O(\lg \lg n)\) query time for points in rank space.

3. We give a randomized algorithm for 4-d offline dominance range reporting/emptiness with running time \(O(n \log n)\) plus the output size. This resolves two open problems (both appeared in F. P. Preparata and M. I. Shamos’s seminal book [Computational geometry. An introduction. New York etc.: Springer-Verlag (1985; Zbl 0575.68059; Zbl 0759.68037)]):

(a) Given a set of \(n\) axis-aligned rectangles in the plane, we can report all \(k\) enclosure pairs (i.e., pairs \((r_{1},r_{2})\) where rectangle \(r_{1}\) completely encloses rectangle \(r_{2}\)) in \(O(n \lg n + k)\) expected time;

(b) Given a set of \(n\) points in 4-d, we can find all maximal points (points not dominated by any other points) in \(O(n \lg n)\) expected time.

The most recent previous development on (a) was reported back in SoCG’95 by P. Gupta et al. [Int. J. Comput. Geom. Appl. 7, No. 5, 437–455 (1997; Zbl 0888.68066)], whose main result was an \(O([n \lg n + k] \lg \lg n)\) algorithm. The best previous result on (b) was an \(O(n \lg n \lg \lg n)\) algorithm due to H. N. Gabow [“Scaling and related techniques for geometry problems”, in: Proceedings of the sixteenth annual ACM symposium on theory of computing, STOC ’84. New York, NY: ACM Press. 135–143 (1984)]. As a consequence, we also obtain the current-record time bound for the maxima problem in all constant dimensions above.

For the entire collection see [Zbl 1271.68010].

Reviewer: Reviewer (Berlin)