Back to Search
Start Over
Dynamic half-space range reporting and its applications.
- Source :
- Algorithmica; Apr1995, Vol. 13 Issue 4, p325-345, 21p
- Publication Year :
- 1995
-
Abstract
- We consider the half-space range-reporting problem: Given a set S of n points in ℝ, 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 and an arbitrarily small positive constant ɛ, we achieve O( m) space and preprocessing time, O(( n/ m log n+k) query time, and O(mn) amortized update time ( d ≳ 3). We present, among others, the following applications: an O(n)-time algorithm for computing convex layers in ℝ, and an output sensitive algorithm for computing a level in an arrangements of planes in ℝ, whose time complexity is O(( b+n) n, where b is the size of the level. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 01784617
- Volume :
- 13
- Issue :
- 4
- Database :
- Complementary Index
- Journal :
- Algorithmica
- Publication Type :
- Academic Journal
- Accession number :
- 71309604
- Full Text :
- https://doi.org/10.1007/BF01293483