@techreport{TD:100303,
	att_abstract={{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(nlglg n)$ space and
  $O(lglg n)$ query time, assuming that the $n$ given points are in
  rank space.
This improves the previous results by Alstrup, Brodal, and Rauhe
(FOCS'00), with $O(nlg^eps n)$ space and $O(lglg n)$ query time,
or with $O(nlglg n)$ space and $O(lg^2lg 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/lg lg n)$ time.

* We give a data structure for 3-d orthogonal range reporting
with $O(nlg^{1+eps} n)$ space and $O(lglg n + k)$ query time
for points in rank space, for any constant $eps>0$.
This improves the previous results by Afshani (ESA'08),
Karpinski and Nekrich (COCOON'09), and Chan (SODA'11),
with $O(nlg^3 n)$ space and $O(lglg n + k)$ query time, or
with $O(nlg^{1+eps}n)$ space and $O(lg^2lg 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 2-d orthogonal range 
minimum queries with $O(nlg^eps n)$ space and $O(lglg n)$ query time
for points in rank space.

* We give a randomized algorithm for 4-d emph{offline} dominance range
reporting/emptiness with running time $O(nlog n)$ plus the output size.
This resolves two open problems (both appeared 
in Preparata and Shamos' seminal book):

**(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(nlg 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(nlg n)$ expected time.

The most recent previous development on (a) was reported back in SoCG'95 by
Gupta, Janardan, Smid, and Dasgupta, whose main result was
an $O([nlg n + k]lglg n)$ algorithm.  The best previous
result on (b) was an $O(nlg nlglg n)$ algorithm
due to Gabow, Bentley, and Tarjan---from STOC'84!
As a consequence, we also obtain the current-record time bound for
the maxima problem in all constant dimensions above~4.
}},
	att_authors={mp6431},
	att_categories={},
	att_copyright={{ACM}},
	att_copyright_notice={{(c) ACM, 2011. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in ACM Symposium on Computational Geometry {{, 2011-06-13}}.
}},
	att_donotupload={},
	att_private={false},
	att_projects={},
	att_tags={},
	att_techdoc={true},
	att_techdoc_key={TD:100303},
	att_url={http://web1.research.att.com:81/techdocs_downloads/TD:100303_DS1_2010-12-02T19:46:37.404Z.pdf},
	author={Mihai Patrascu and Timothy M. Chan and Kasper Green Larsen},
	institution={{ACM Symposium on Computational Geometry}},
	month={June},
	title={{Orthogonal Range Searching on the RAM, Revisited}},
	year=2011,
}