Halfspace range search: An algorithmic application ofk-sets

Given a fixed setS ofn points inE ³ and a query plane, the halfspace range search problem asks for the retrieval of all points ofS on a chosen side of. We prove that withO(n(logn)⁸ (loglogn)⁴) storage it is possible to solve this problem inO(k+logn) time, wherek is the number of points to be reported. This result rests crucially on a new combinatorial derivation. We show that the total number ofj-sets (j=1, ...,k) realized by a set ofn points inE ³ isO(nk ⁵); ak-set is any subset ofS of sizek which can be separated from the rest ofS by a plane.Supported in part by NSF grants MCS 83-03925 and the Office of Naval Research and the Defense Advanced Research Projects Agency under contract N00014-83-K-0146 and ARPA Order No. 4786.Supported in part by Joint Services Electronics Program under Contract N00014-79-C-0424.