DYNAMIC HALF-SPACE RANGE REPORTING AND ITS APPLICATIONS

We consider the half-space range-reporting problem: Given a set S of n points in R(d), preprocess it into a data structure, so that, given a query half-space gamma, all k points of S boolean AND gamma 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 less than or equal to m less than or equal to n([d/2]) and an arbitrarily small positive constant epsilon, we achieve O(m(1+epsilon)) space and preprocessing time, O((n/m([d/2])) log n + k) query time, and O(m(1+epsilon)/n) amortized update time (d greater than or equal to 3). We present, among others, the following applications: an O(n(1+epsilon))-time algorithm for computing convex layers in R(3), and an output sensitive algorithm for computing a level in an arrangements of planes in R(3), whose time complexity is O((b + n). n(epsilon)), where b is the size of the level.