Generalized static orthogonal range searching in less space

TR-2003-33, Author: Christian Worm Mortensen

Christian Worm Mortesen

September 2003

Abstract

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.