TY - GEN

T1 - Halfspace range search

T2 - 1st Annual Symposium on Computational Geometry, SCG 1985

AU - Chazelle, Bernard

AU - Preparata, Franco P.

N1 - Publisher Copyright:
© 1985 ACM.

PY - 1985/6/1

Y1 - 1985/6/1

N2 - Given a fixed set S of n points in E∗ and a query plane the halfspace range search problem asks for the retrieval of all points of 5 on a chosen side of x. We prove that with 0(n(logn)8(loglogn)4) storage it is posAsible to solve this problem ia 0(k 4- logn) time, where k is the number of points to be reported. This result rests crucially on a new combinatorial derivation. We show that the maximum number of Ar-sets realized by a set of n points in E is 0(nfce) for a small positive constant c; a fc-set is any subset of S of size k which can be separated from the rest of S by a plane. Incidentally, this result constitutes the only nontrivial upper bound, as a function of n and k, known to date.

AB - Given a fixed set S of n points in E∗ and a query plane the halfspace range search problem asks for the retrieval of all points of 5 on a chosen side of x. We prove that with 0(n(logn)8(loglogn)4) storage it is posAsible to solve this problem ia 0(k 4- logn) time, where k is the number of points to be reported. This result rests crucially on a new combinatorial derivation. We show that the maximum number of Ar-sets realized by a set of n points in E is 0(nfce) for a small positive constant c; a fc-set is any subset of S of size k which can be separated from the rest of S by a plane. Incidentally, this result constitutes the only nontrivial upper bound, as a function of n and k, known to date.

UR - http://www.scopus.com/inward/record.url?scp=79955737504&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=79955737504&partnerID=8YFLogxK

U2 - 10.1145/323233.323248

DO - 10.1145/323233.323248

M3 - Conference contribution

AN - SCOPUS:79955737504

T3 - Proceedings of the 1st Annual Symposium on Computational Geometry, SCG 1985

SP - 107

EP - 115

BT - Proceedings of the 1st Annual Symposium on Computational Geometry, SCG 1985

PB - Association for Computing Machinery, Inc

Y2 - 5 June 1985 through 7 June 1985

ER -