# Dynamic half-space range reporting and its applications

Published

Journal Article

We consider the half-space range-reporting problem: Given a set S of n points in ℝ d , preprocess it into a data structure, so that, given a query half-space γ, 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(m 1+e{open} ) space and preprocessing time, O((n/m ⌊d/2⌋ log n+k) query time, and O(m 1+e{open} n) amortized update time (d ≳ 3). We present, among others, the following applications: an O(n 1+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) n e{open} , where b is the size of the level. © 1995 Springer-Verlag New York Inc.

### Full Text

### Duke Authors

### Cited Authors

- Agarwal, PK; Matoušek, J

### Published Date

- April 1, 1995

### Published In

### Volume / Issue

- 13 / 4

### Start / End Page

- 325 - 345

### Electronic International Standard Serial Number (EISSN)

- 1432-0541

### International Standard Serial Number (ISSN)

- 0178-4617

### Digital Object Identifier (DOI)

- 10.1007/BF01293483

### Citation Source

- Scopus