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+e)+k) time, where k is the number of reported answers. This is optimal up to the factor O(n~e). If the c-dops in S may intersect, the query time becomes O(n1–1/c+k), which is optimal.
展开▼
机译：C-DOP是C取向凸多托，即凸多孔孔，其边缘具有来自固定的C取向的取向。在本文中，我们研究了使用C-DOPS作为边界卷的DOP树限制体积层次。我们证明，对于平面中的n个不相交的c-dops的任何组，可以构建一个dop树，使得在o（n〜（1/2 +）中可以回答使用c-dop的范围查询e）+ k）时间，其中k是报告答案的数量。这是最佳的因子O（n〜e）。如果S中的C-DOP可以相交，则查询时间变为O（n1-1 / c + k），这是最佳的。
展开▼
