Efficient c-oriented range searching with DOP-trees

M. Berg, de, H.J. Haverkort, M.W.A. Streppel

Research output: Contribution to journalArticleAcademicpeer-review

1 Citation (Scopus)
1 Downloads (Pure)


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.
Original languageEnglish
Pages (from-to)250-267
JournalComputational Geometry
Issue number3
Publication statusPublished - 2009


Dive into the research topics of 'Efficient c-oriented range searching with DOP-trees'. Together they form a unique fingerprint.

Cite this