Efficient c-oriented range searching with DOP-trees

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

doi:10.1007/11561071_46

Efficient c-oriented range searching with DOP-trees

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

Algorithms

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

3 Citations (Scopus)

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.

Original language	English
Title of host publication	Algorithms - ESA 2005
Subtitle of host publication	13th Annual European Symposium, Palma de Mallorca, Spain, October 3-6, 2005. Proceedings
Editors	G.S. Brodal, S. Leonardi
Place of Publication	Berlin
Publisher	Springer
Chapter	46
Pages	508-519
Number of pages	12
ISBN (Electronic)	978-3-540-31951-1
ISBN (Print)	3-540-29118-0, 978-3-540-29118-3
DOIs	https://doi.org/10.1007/11561071_46
Publication status	Published - 2005

Publication series

Name	Lecture Notes in Computer Science (LNCS)
Volume	3669
ISSN (Print)	0302-9743

Access to Document

10.1007/11561071_46

Cite this

Berg, de, M., Haverkort, H. J., & Streppel, M. W. A. (2005). Efficient c-oriented range searching with DOP-trees. In G. S. Brodal, & S. Leonardi (Eds.), Algorithms - ESA 2005 : 13th Annual European Symposium, Palma de Mallorca, Spain, October 3-6, 2005. Proceedings (pp. 508-519). (Lecture Notes in Computer Science (LNCS); Vol. 3669). Springer. https://doi.org/10.1007/11561071_46

@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{\textemdash}bounding-volume hierarchies that use c-dops as bounding volumes{\textemdash}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",

}

Efficient c-oriented range searching with DOP-trees. / Berg, de, M.; Haverkort, H.J.; Streppel, M.W.A.
Algorithms - ESA 2005 : 13th Annual European Symposium, Palma de Mallorca, Spain, October 3-6, 2005. Proceedings. ed. / G.S. Brodal; S. Leonardi. Berlin: Springer, 2005. p. 508-519 (Lecture Notes in Computer Science (LNCS); Vol. 3669).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

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

AU - Berg, de, M.

AU - Haverkort, H.J.

AU - Streppel, M.W.A.

PY - 2005

Y1 - 2005

N2 - 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.

AB - 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.

U2 - 10.1007/11561071_46

DO - 10.1007/11561071_46

M3 - Conference contribution

SN - 3-540-29118-0

SN - 978-3-540-29118-3

T3 - Lecture Notes in Computer Science (LNCS)

SP - 508

EP - 519

BT - Algorithms - ESA 2005

A2 - Brodal, G.S.

A2 - Leonardi, S.

PB - Springer

CY - Berlin

ER -

Efficient c-oriented range searching with DOP-trees

Abstract

Publication series

Access to Document

Fingerprint

Cite this