Approximate range searching using binary space partitions

摘要

We show how any BSP tree T-P 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(T-P)) 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 0(n log n) such that E-approximate range searching queries with any constant-complexity convex query range can be answered in O(mins(epsilon > 0){(1/epsilon) + k(epsilon)} log n) time, where k(epsilon) is the number of segments intersecting the e-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.