TY - JOUR

T1 - Efficient c-oriented range searching with DOP-trees

AU - Berg, de, M.

AU - Haverkort, H.J.

AU - Streppel, M.W.A.

PY - 2009

Y1 - 2009

N2 - 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+e+k) time in the worst case, when c and e are constant. This is optimal up to the factor O(ne). 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.

AB - 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+e+k) time in the worst case, when c and e are constant. This is optimal up to the factor O(ne). 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.

U2 - 10.1016/j.comgeo.2008.05.002

DO - 10.1016/j.comgeo.2008.05.002

M3 - Article

VL - 42

SP - 250

EP - 267

JO - Computational Geometry

JF - Computational Geometry

SN - 0925-7721

IS - 3

ER -