2009.09.14 | Else Magård

Title: Orthogonal Range Reporting in Three and Higher Dimensions

Speaker: Kasper Dalgaard Larsen, Aarhus University

Abstract:
In orthogonal range reporting we are to preprocess N points in d-dimensional space so that the points inside a d-dimensional axis-aligned query box can be reported efficiently. This is a fundamental problem in various fields, including spatial databases and computational geometry.

In this talk we show a number of improvements for three and higher dimensional orthogonal range reporting:
In the pointer machine model, we improve all the best previous results, some of which have not seen any improvements in almost two decades.
In the I/O-model, we improve the previously known three-dimensional structures and provide the first (nontrivial) structures for four and higher dimensions.

Joint work with: Peyman Afshani, Lars Arge

Host: Gerth Stølting Brodal SK: 5211