Approximate range searching using binary space partitions

We show how any BSP tree TP for the endpoints of a set of n disjoint segments in the plane can be used to obtain a BSP tree of size O(n⋅depth(TP)) 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 Rd 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.