Generalized static orthogonal range searching in less space
TR-2003-33, Author: Christian Worm Mortensen Christian Worm Mortesen
We reduce the space usage on two problems related to generalized orthogonal range searching by almost a logarithmic factor. Our main result is that the generalized static orthogonal segment intersection reporting problem for n segment on an n times n grid can be solved in time O(log 2 log n + k) for queries using space O(n log log n). Here k is the number of reported segments.
Technical report TR-2003-33 in IT University Technical Report Series, September 2003.
Available as PDF