An optimal dynamic interval stabbing-max data structure?


Journal Article

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 ℝd, where each rectangle s ∈ 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.

Duke Authors

Cited Authors

  • Agarwal, PK; Arge, L; Yi, K

Published Date

  • July 1, 2005

Published In

  • Proceedings of the Annual Acm Siam Symposium on Discrete Algorithms

Start / End Page

  • 803 - 812

Citation Source

  • Scopus