Computer Science – Computational Geometry
Scientific paper
2011-03-28
Computer Science
Computational Geometry
To appear in SoCG 2011
Scientific paper
We present several 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 for points in rank space: ** We present two data structures for 2-d orthogonal range emptiness. The first achieves O(n lglg n) space and O(lglg n) query time. This improves the previous results by Alstrup, Brodal, and Rauhe(FOCS'00), with O(n lg^eps n) space and O(lglg n) query time, or with O(nlglg n) space and O(lg^2 lg n) query time. Our second data structure uses O(n) space and answers queries in O(lg^eps n) time. The best previous O(n)-space data structure, due to Nekrich (WADS'07), answers queries in O(lg n/lglg n) time. ** For 3-d orthogonal range reporting, we obtain space O(n lg^{1+eps} n) and query time O(lglg n + k), for any constant eps>0. This improves previous results by Afshani (ESA'08), Karpinski and Nekrich (COCOON'09), and Chan (SODA'11), with O(n lg^3 n) space and O(lglg n + k) query time, or with O(n lg^{1+eps} n) space and O(lg^2 lg n + k) query time. This implies improved bounds for orthogonal range reporting in all constant dimensions above 3. ** We give a randomized algorithm for 4-d offline dominance range reporting/emptiness with running time O(n lg n + k). This resolves two open problems from Preparata and Shamos' seminal book: **** given n axis-aligned rectangles in the plane, we can report all k enclosure pairs in O(n lg n + k) expected time. The best known result was an O([n lg n + k] lglg n) algorithm from SoCG'95 by Gupta, Janardan, Smid, and Dasgupta. **** given n points in 4-d, we can find all maximal points in O(n lg n) expected time. The best previous result was an O(n lg n lglg n) algorithm due to Gabow, Bentley, and Tarjan (STOC'84). This implies record time bounds for the maxima problem in all constant dimensions above 4.
Chan Timothy M.
Larsen Kasper Green
Patrascu Mihai
No associations
LandOfFree
Orthogonal Range Searching on the RAM, Revisited does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Orthogonal Range Searching on the RAM, Revisited, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Orthogonal Range Searching on the RAM, Revisited will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-162389