### Abstract

Given a fixed set S of n points in E^{3} 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 E^{3} is O(nk^{5}); 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 1 1986 |

Externally published | Yes |

### All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Geometry and Topology
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics

## Fingerprint Dive into the research topics of 'Halfspace range search: An algorithmic application of k-sets'. Together they form a unique fingerprint.

## Cite this

Chazelle, B., & Preparata, F. P. (1986). Halfspace range search: An algorithmic application of k-sets.

*Discrete & Computational Geometry*,*1*(1), 83-93. https://doi.org/10.1007/BF02187685