@inproceedings{d43616fc5a7b49c7bfed4f82ec49c5cc,

title = "Efficient c-oriented range searching with DOP-trees",

abstract = "A c-dop is a c-oriented convex polytope, that is, a convex polytope whose edges have orientations that come from a fixed set of c 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 a range query with a c-dop as query range can be answered in O(n 1/2 + ε + k) time, where k is the number of reported answers. This is optimal up to the factor O(n ε ). If the c-dops in S may intersect, the query time becomes O(n 1−1/c+k), which is optimal.",

author = "{Berg, de}, M. and H.J. Haverkort and M.W.A. Streppel",

year = "2005",

doi = "10.1007/11561071_46",

language = "English",

isbn = "3-540-29118-0",

series = "Lecture Notes in Computer Science (LNCS)",

publisher = "Springer",

pages = "508--519",

editor = "G.S. Brodal and S. Leonardi",

booktitle = "Algorithms - ESA 2005",

address = "Germany",

}