Efficient c-oriented range searching with DOP-trees

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

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

2 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 languageEnglish
Title of host publicationAlgorithms - ESA 2005
Subtitle of host publication13th Annual European Symposium, Palma de Mallorca, Spain, October 3-6, 2005. Proceedings
EditorsG.S. Brodal, S. Leonardi
Place of PublicationBerlin
PublisherSpringer
Chapter46
Pages508-519
Number of pages12
ISBN (Electronic)978-3-540-31951-1
ISBN (Print)3-540-29118-0, 978-3-540-29118-3
DOIs
Publication statusPublished - 2005

Publication series

NameLecture Notes in Computer Science (LNCS)
Volume3669
ISSN (Print)0302-9743

Fingerprint

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

Cite this