Orthogonal Range Searching in Linear and Almost-Linear Space | SpringerLink
Skip to main content
Springer Nature Link
Log in

Orthogonal Range Searching in Linear and Almost-Linear Space

  • Conference paper
Algorithms and Data Structures (WADS 2007)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 4619))

Included in the following conference series:

Abstract

In this paper we describe space-efficient data structures for two-dimensional range searching problem.

We present a dynamic linear space data structure that supports orthogonal range reporting queries in O(logn + klogε n) time, where k is the size of the answer. Our data structure also supports emptiness and one-reporting queries in O(logn) time and thus achieves optimal time and space for this type of queries. In the case of integer point coordinates, we describe a static linear space data structure that supports range reporting queries in O(logn/loglogn + klogε n) time and emptiness and one-reporting queries in O(logn/loglogn) time. This is the first linear space data structure for these problems that achieves sub-logarithmic query time.

We also present a dynamic linear space data structure for range counting queries with O((logn/loglogn)2) time and a dynamic O(nlogn/loglogn) space data structure for semi-group range sum queries with query time O((logn/loglogn)2).

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

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Alstrup, S., Brodal, G.S., Rauhe, T.: New Data Structures for Orthogonal Range Searching. In: Proc. 41st FOCS 2000, pp. 198–207 (2000)

    Google Scholar 

  2. Arge, L., Vitter, J.S.: Optimal External Memory Interval Management. SIAM J. on Computing 32(6), 1488–1508 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  3. Bender, M.A., Cole, R., Demaine, E.D., Farach-Colton, M., Zito, J.: Two Simplified Algorithms for Maintaining Order in a List. In: Möhring, R.H., Raman, R. (eds.) ESA 2002. LNCS, vol. 2461, pp. 152–164. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

  4. Bentley, J.L.: Multidimensional Divide-and-Conquer. Commun. ACM 23, 214–229 (1980)

    Article  MATH  MathSciNet  Google Scholar 

  5. Blandford, D.K., Blelloch, G.E.: Compact Representations of Ordered Sets. In: Proc. 15th SODA 2004, pp. 11–19 (2004)

    Google Scholar 

  6. Chazelle, B.: A Functional Approach to Data Structures and its Use in Multidimensional Searching. SIAM J. on Computing 17, 427–462 (1988)

    Article  MATH  MathSciNet  Google Scholar 

  7. Elias, P.: Universal Codeword Sets and Representations of the Integers. IEEE Transactions on Information Theory 21, 194–203 (1975)

    Article  MATH  MathSciNet  Google Scholar 

  8. van Emde Boas, P.: Preserving Order in a Forest in Less Than Logarithmic Time and Linear Space. Inf. Process. Lett. 6(3), 80–82 (1977)

    Article  MATH  Google Scholar 

  9. van Emde Boas, P., Kaas, R., Zijlstra, E.: Design and Implementation of an Efficient Priority Queue. Mathematical Systems Theory 10, 99–127 (1977)

    Article  MATH  Google Scholar 

  10. Itai, A., Konheim, A.G., Rodeh, M.: A Sparse Table Implementation of Priority Queues. In: Even, S., Kariv, O. (eds.) ICALP 1981. LNCS, vol. 115, pp. 417–431. Springer, Heidelberg (1981)

    Google Scholar 

  11. Van Kreveld, M., Overmars, M.H.: Divided K-d Trees. Algorithmica 6(6), 840–858 (1991)

    Article  MATH  MathSciNet  Google Scholar 

  12. Mehlhorn, K.: Data Structures and Algorithms 1: Sorting and Searching. Springer, Heidelberg (1984)

    MATH  Google Scholar 

  13. Mortensen, C.W.: Fully Dynamic Orthogonal Range Reporting on RAM. SIAM J. on Computing 35, 1494–1525 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  14. Nekrich, Y.: Space Efficient Dynamic Orthogonal Range Reporting. In: Proc. 21st SoCG 2005, pp. 306–313 (2005)

    Google Scholar 

  15. Nekrich, Y.: A Linear Space Data Structure for Orthogonal Range Reporting and Emptiness Queries. In: Proc. 18th CCCG 2006, pp. 159–163 (2006)

    Google Scholar 

  16. Mortensen, C.W., Pagh, R., Pǎtraşcu, M.: On Dynamic Range Reporting in One Dimension. In: Proc. 37th STOC 2005, pp. 104–111 (2005)

    Google Scholar 

  17. Pǎtraşcu, M.: Lower Bounds for 2-Dimensional Range Counting. In: Proc. 39th STOC 2007 (to appear)

    Google Scholar 

  18. Pǎtraşcu, M., Demaine, E.D.: Tight Bounds for the Partial-Sums Problem. In: Proc. 15th SODA 2004, pp. 20–29 (2004)

    Google Scholar 

  19. Willard, D.E.: A Density Control Algorithm for Doing Insertions and Deletions in a Sequentially Ordered File in Good Worst-Case Time. Information and Computation 97, 150–204 (1992)

    Article  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, University of Bonn,  

    Yakov Nekrich

Authors
  1. Yakov Nekrich
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Frank Dehne Jörg-Rüdiger Sack Norbert Zeh

Rights and permissions

Reprints and permissions

Copyright information

© 2007 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Nekrich, Y. (2007). Orthogonal Range Searching in Linear and Almost-Linear Space. In: Dehne, F., Sack, JR., Zeh, N. (eds) Algorithms and Data Structures. WADS 2007. Lecture Notes in Computer Science, vol 4619. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-73951-7_3

Download citation

  • DOI: https://doi.org/10.1007/978-3-540-73951-7_3

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-73948-7

  • Online ISBN: 978-3-540-73951-7

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation