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 O(n log n) such that ε-approximate range searching queries with any constant-complexity convex query range can be answered in O(min_(ε > 0){(1/ε) + κ_ε} log n) time, where κ_ε 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 R~d such that ε-approximate range searching with any constant-complexity convex query range can be done in O(log n + min_ε > 0{(1/ε~(d-1)) + κ_ε}) time.
展开▼
