Approximate range searching using binary space partitions

M. Berg, de, M.W.A. Streppel

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

5 Citations (Scopus)

Abstract

We show how any BSP tree T P for the endpoints of a set of n disjoint segments in the plane can be used to obtain a BSP tree of size O(n.depth(T P )) for the segments themselves, such that the range-searching efficiency remains almost the same. We apply this technique to obtain a BSP tree of size O(n log n) such that e-approximate range searching queries with any constant-complexity convex query range can be answered in O(min e>¿0{1/e¿+¿k e }log n) time, where k e is the number of segments intersecting the e-extended range. The same result can be obtained for disjoint constant-complexity curves, if we allow the BSP to use splitting curves along the given curves. We also describe how to construct a linear-size BSP tree for low-density scenes consisting of n objects in R d such that e-approximate range searching with any constant-complexity convex query range can be done in O(logn+min ¿>0 {1/¿ (d-1) +k ¿ }) time.
Original languageEnglish
Title of host publicationFoundations of Software Technology and Theoretical Computer Science (Proceedings 24th Conference, FSTTCS 2004, Chennai, India, December 16-18, 2004)
EditorsK. Lodaya, M. Mahajan
Place of PublicationBerlin
PublisherSpringer
Pages110-121
ISBN (Print)3-540-24058-6
DOIs
Publication statusPublished - 2004

Publication series

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

Fingerprint Dive into the research topics of 'Approximate range searching using binary space partitions'. Together they form a unique fingerprint.

  • Cite this

    Berg, de, M., & Streppel, M. W. A. (2004). Approximate range searching using binary space partitions. In K. Lodaya, & M. Mahajan (Eds.), Foundations of Software Technology and Theoretical Computer Science (Proceedings 24th Conference, FSTTCS 2004, Chennai, India, December 16-18, 2004) (pp. 110-121). (Lecture Notes in Computer Science; Vol. 3328). Springer. https://doi.org/10.1007/978-3-540-30538-5_10