Abstract
Given a fixed set S of n points in E3 and a query plane π, the halfspace range search problem asks for the retrieval of all points of S on a chosen side of π. We prove that with O(n(log n)8 (loglog n)4) storage it is possible to solve this problem in O(k+log n) time, where k is the number of points to be reported. This result rests crucially on a new combinatorial derivation. We show that the total number of j-sets (j=1, ..., k) realized by a set of n points in E3 is O(nk5); a k-set is any subset of S of size k which can be separated from the rest of S by a plane.
Original language | English (US) |
---|---|
Pages (from-to) | 83-93 |
Number of pages | 11 |
Journal | Discrete & Computational Geometry |
Volume | 1 |
Issue number | 1 |
DOIs | |
State | Published - Dec 1986 |
Externally published | Yes |
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Geometry and Topology
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics