Skip to main content
SpringerLink
Log in

Efficient worst-case data structures for range searching

  • Published:
Acta Informatica Aims and scope Submit manuscript

Abstract

In this paper we investigate the worst-case complexity of range searching: preprocess N points in k-space such that range queries can be answered quickly. A range query asks for all points with each coordinate in some range of values, and arises in many problems in statistics and data bases. We develop three different structures for range searching in this paper. The first structure has absolutely optimal query time (which we prove), but has very high preprocessing and storage costs. The second structure we present has logarithmic query time and O(N 1+2) preprocessing and storage costs, for any fixed ɛ>0. Finally we give a structure with linear storage, O(N ln N) preprocessing and O(N ɛ) query time.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Bentley, J.L.: Multidimensional binary search trees used for associative searching. Comm. ACM 18, 509–517 (1975)

    Article  Google Scholar 

  2. Bentley, J.L.: Multidimensional Divide-Conquer. Carnegie Mellon University Computer Science Department Research Review, 1978, pp. 7–24

  3. Bentley, J.L., Friedman. J.H.: Data structures for range searching. Comput. Surveys (in press 1980)

  4. Knuth, D.E.: The Art of Computer Programming, vol.3. Reading, Mass.: Addison-Wesley 1973

    MATH  Google Scholar 

  5. Lee, D.T., Wong, C.K.: Worst case analysis for region and partial region searches in multidimensional binary search trees and balanced quad trees. Acta Informatica 9, 23–29 (1977)

    Article  MathSciNet  Google Scholar 

  6. Maurer, H.A., Ottmann, Th.: Manipulating sets of points — a survey In: Graphen, Algorithmen, Datenstrukturen: Workshop 78, München-Wien: Hanser 1978

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Departments of Computer Science and Mathematics, Carnegie-Mellon University, 15213, Pittsburgh, PA, USA

    J. L. Bentley

  2. Institut für Informationsverarbeitung, Technische Universität Graz, Steyrergasse 17, A-8010, Graz, Austria

    H. A. Maurer

Authors
  1. J. L. Bentley
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. H. A. Maurer
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

Research in this paper has been supported partially under Office of Naval Research contract N000014-76-C-0373, USA, and by the Austrian Federal Ministry for Science and Research

Rights and permissions

Reprints and permissions

About this article

Cite this article

Bentley, J.L., Maurer, H.A. Efficient worst-case data structures for range searching. Acta Informatica 13, 155–168 (1980). https://doi.org/10.1007/BF00263991

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF00263991

Keywords

Search

Navigation