Title: Recent Developments on Orthogonal Range Reporting

Author: Peyman Afshani

Date: June 10, 2010

Abstract:
Orthogonal range reporting is the problem of storing a set of n points
in d-dimensional space, such that the k points in an axis-orthogonal query
box can be reported efficiently. This is a fundamental problem in various
fields such as databases and computational geometry and has been studied
extensively in the past decades.

We will briefly discuss some of the recent improvements on the problem,
including the best data structures with polylogarithmic query time in
dimensions greater than two and in the I/O-model and the pointer machine 
model, as well as the first non-trivial query lower bound.

At the end, we shall discuss some intriguing open problems that come
from these results.