Efficient c-oriented range searching with DOP-trees

A c-dop is a c-oriented convex polytope, that is, a convex polytope whose facets have orientations that come from a fixed set of c (undirected) orientations. In this paper we study dop-trees—bounding-volume hierarchies that use c-dops as bounding volumes—in the plane. We prove that for any set S of n disjoint c-dops in the plane, one can construct a dop-tree such that all k dops in S that intersect any given query c-dop can be retrieved in O(n1/2+ε+k) time in the worst case, when c and ε are constant. This is optimal up to the factor O(nε). The same query time can be achieved when the c-dops do not intersect too heavily, that is, when any point in the plane is contained in only a constant number of c-dops. When the c-dops in S may intersect arbitrarily, the worst-case query time becomes O(n1−1/c+k), which is optimal.