Math @ Duke

Publications [#235396] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Matoušek, J, Dynamic halfspace range reporting and its applications,
Algorithmica, vol. 13 no. 4
(1995),
pp. 325345, ISSN 01784617 [doi]
(last updated on 2018/05/21)
Abstract: We consider the halfspace rangereporting problem: Given a set S of n points in ℝd, preprocess it into a data structure, so that, given a query halfspace γ, all k points of S ∩ γ can be reported efficiently. We extend previously known static solutions to dynamic ones, supporting insertions and deletions of points of S. For a given parameter m, n ≤m ≤n⌊d/2⌋ and an arbitrarily small positive constant e{open}, we achieve O(m1+e{open}) space and preprocessing time, O((n/m⌊d/2⌋ log n+k) query time, and O(m1+e{open}n) amortized update time (d ≳ 3). We present, among others, the following applications: an O(n1+e{open})time algorithm for computing convex layers in ℝ3, and an output sensitive algorithm for computing a level in an arrangements of planes in ℝ3, whose time complexity is O((b+n) ne{open}, where b is the size of the level. © 1995 SpringerVerlag New York Inc.


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

