Math @ Duke

Publications [#235547] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Arge, L; Kaplan, H; Molad, E; Tarjan, RE; Yi, K, An optimal dynamic data structure for stabbingsemigroup queries,
SIAM Journal on Computing, vol. 41 no. 1
(2012),
pp. 104127, ISSN 00975397 [doi]
(last updated on 2018/02/20)
Abstract: Let S be a set of n intervals in ℝ, and let (S,+) be any commutative semigroup. We assign a weight ω(s) ε S to each interval in S. For a point x ε ℝ, let S(x) C S be the set of intervals that contain x. Given a point q ε ℝ, the stabbingsemigroup query asks for computing ΣsεS(q) ω(s). We propose a linearsize dynamic data structure, under the pointermachine model, that answers queries in worstcase O(log n) time and supports both insertions and deletions of intervals in amortized O(log n) time. It is the first data structure that attains the optimal O(log n) bound for all three operations. Furthermore, our structure can easily be adapted to external memory, where we obtain a linearsize structure that answers queries and supports updates in O(log Bn) I/Os, where B is the disk block size. For the restricted case of a nested family of intervals (either every pair of intervals is disjoint or one contains the other), we present a simpler solution based on dynamic trees. © 2012 Society for Industrial and Applied Mathematics.


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

