I/O-Efficient Structures for Orthogonal Range-Max and Stabbing-Max Queries

Pankaj K. Agarwal, Lars Arge, Jun Yang, and Ke Yi

Proceedings of the 11th European Symposium on Algorithms (ESA '03), pages 7-18, Budapest, Hungary, September 2003.

Abstract

We develop several linear or near-linear space and I/O-efficient dynamic data structures for orthogonal range-max queries and stabbing-max queries. Given a set of N weighted points in R^d, the range-max problem asks for the maximum-weight point in a query hyper-rectangle. In the dual stabbing-max problem, we are given N weighted hyper-rectangles, and we wish to find the maximum-weight rectangle containing a query point. Our structures improve on previous structures in several important ways.

Papers

Conference version: [SpringerLink download]
Full version:

Presentations

ESA '03, Budapest, Hungary, September 2003 (given by );
Duke CS Algorithms Seminar, January, 2003. Slides:

Copyright notice

© Springer-Verlag Berlin Heidelberg 2003.

Last modified 07/19/05