### Abstract

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.

Original language | English (US) |
---|---|

Title of host publication | Proceedings of the 1st Annual Symposium on Computational Geometry, SCG 1985 |

Publisher | Association for Computing Machinery, Inc |

Pages | 107-115 |

Number of pages | 9 |

ISBN (Electronic) | 0897911636, 9780897911634 |

DOIs | |

State | Published - Jun 1 1985 |

Externally published | Yes |

Event | 1st Annual Symposium on Computational Geometry, SCG 1985 - Baltimore, United States Duration: Jun 5 1985 → Jun 7 1985 |

### Publication series

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

### Other

Other | 1st Annual Symposium on Computational Geometry, SCG 1985 |
---|---|

Country | United States |

City | Baltimore |

Period | 6/5/85 → 6/7/85 |

### All Science Journal Classification (ASJC) codes

- Computational Mathematics
- Geometry and Topology

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

## Cite this

*Proceedings of the 1st Annual Symposium on Computational Geometry, SCG 1985*(pp. 107-115). (Proceedings of the 1st Annual Symposium on Computational Geometry, SCG 1985). Association for Computing Machinery, Inc. https://doi.org/10.1145/323233.323248