Pankaj K. Agarwal, Lars Arge, and Ke Yi
Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '05), Vancouver, BC, Canada, January 2005, 803-812.
In this paper we consider the dynamic stabbing-max problem, that is, the problem of dynamically maintaining a set S of n axis-parallel hyper-rectangles in Rd, where each rectangle s of S has a weight w(s), so that the rectangle with the maximum weight containing a query point can be determined efficiently. We develop a linear-size structure for the one-dimensional version of the problem, the interval stabbing-max problem, that answers queries in worst-case O(log n) time and supports updates in amortized O(log n) time. Our structure works in the pointer-machine model of computation and utilizes many ingredients from recently developed external memory structures. Using standard techniques, our one-dimensional structure can be extended to higher dimensions, while paying a logarithmic factor in space, update time, and query time per dimension. Furthermore, our structure can easily be adapted to external memory, where we obtain a linear-size structure that answers queries and supports updates in O(logB n) I/Os, where B is the disk block size.
Conference version: [acm
download]
Department of Computer Science, University of Aarhus, Aarhus, Denmark,
October, 2005.
SODA '05, Vancouver, BC, Canada, January 2005. Slides: 
Duke CS Algorithms Seminar, October 2004.
© Association for Computer Machinery and the Society for Industrial and Applied Mathematics 2005.