Department of Mathematics
 Search | Help | Login | pdf version | printable version

Math @ Duke



Publications [#235470] of Pankaj K. Agarwal

Papers Published

  1. Agarwal, PK; Arge, L; Yi, K, An optimal dynamic interval stabbing-max data structure?, Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (2005), pp. 803-812
    (last updated on 2018/11/18)

    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.
ph: 919.660.2800
fax: 919.660.2821

Mathematics Department
Duke University, Box 90320
Durham, NC 27708-0320