### Abstract

We show how any BSP tree for the endpoints of a set of n disjoint segments in the plane can be used to obtain a BSP tree of size for the segments themselves, such that the range-searching efficiency remains almost the same. We apply this technique to obtain a BSP tree of size O(nlogn) such that -approximate range searching queries with any constant-complexity convex query range can be answered in O(min>0{(1/)+k}logn) time, where k is the number of segments intersecting the -extended range. The same result can be obtained for disjoint constant-complexity curves, if we allow the BSP to use splitting curves along the given curves.
We also describe how to construct a linear-size BSP tree for low-density scenes consisting of n objects in such that -approximate range searching with any constant-complexity convex query range can be done in O(logn+min>0{(1/d-1)+k}) time.

Original language | English |
---|---|

Pages (from-to) | 139-151 |

Journal | Computational Geometry |

Volume | 33 |

Issue number | 3 |

DOIs | |

Publication status | Published - 2006 |

## Fingerprint Dive into the research topics of 'Approximate range searching using binary space partitions'. Together they form a unique fingerprint.

## Cite this

Berg, de, M., & Streppel, M. W. A. (2006). Approximate range searching using binary space partitions.

*Computational Geometry*,*33*(3), 139-151. https://doi.org/10.1016/j.comgeo.2005.08.003