Math @ Duke

Publications [#235470] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Arge, L; Yi, K, An optimal dynamic interval stabbingmax data structure?,
Proceedings of the Annual ACMSIAM Symposium on Discrete Algorithms
(2005),
pp. 803812
(last updated on 2017/12/12)
Abstract: In this paper we consider the dynamic stabbingmax problem, that is, the problem of dynamically maintaining a set S of n axisparallel hyperrectangles 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 linearsize structure for the onedimensional version of the problem, the interval stabbingmax problem, that answers queries in worstcase O(log n) time and supports updates in amortized O(log n) time. Our structure works in the pointermachine model of computation and utilizes many ingredients from recently developed external memory structures. Using standard techniques, our onedimensional 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 linearsize structure that answers queries and supports updates in O(logB n) I/Os, where B is the disk block size.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

