Document Open Access Logo

Dynamic Orthogonal Range Searching on the RAM, Revisited

Authors Timothy M. Chan, Konstantinos Tsakalidis

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2017.28.pdf
  • Filesize: 486 kB
  • 13 pages

Document Identifiers

Author Details

Timothy M. Chan
Konstantinos Tsakalidis

Cite As Get BibTex

Timothy M. Chan and Konstantinos Tsakalidis. Dynamic Orthogonal Range Searching on the RAM, Revisited. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 28:1-28:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.SoCG.2017.28

Abstract

We study a longstanding problem in computational geometry: 2-d dynamic orthogonal range reporting.  We present a new data structure achieving O(log n / log log n + k) optimal query time and O(log^{2/3+o(1)}n) update time (amortized) in the word RAM model, where n is the number of data points and k is the output size.  This is the first improvement in over 10 years of Mortensen's previous result [SIAM J. Comput., 2006], which has O(log^{7/8+epsilon}n) update time for an arbitrarily small constant epsilon.

In the case of 3-sided queries, our update time reduces to O(log^{1/2+epsilon}n), improving Wilkinson's previous bound [ESA 2014] of O(log^{2/3+epsilon}n).

Subject Classification

Keywords
  • dynamic data structures
  • range searching
  • computational geometry

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Stephen Alstrup, Gerth Stølting Brodal, and Theis Rauhe. New data structures for orthogonal range searching. In Proceedings of the 41st Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 198-207, 2000. URL: http://dx.doi.org/10.1109/SFCS.2000.892088.
  2. Stephen Alstrup, Thore Husfeldt, and Theis Rauhe. Marked ancestor problems. In Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 534-543, Nov 1998. URL: http://dx.doi.org/10.1109/SFCS.1998.743504.
  3. Arne Andersson and Mikkel Thorup. Dynamic ordered sets with exponential search trees. Journal of the ACM, 54(3):13, 2007. URL: http://dx.doi.org/10.1145/1236457.1236460.
  4. Lars Arge. The buffer tree: A technique for designing batched external data structures. Algorithmica, 37(1):1-24, 2003. URL: http://dx.doi.org/10.1007/s00453-003-1021-x.
  5. Lars Arge and Jeffrey Scott Vitter. Optimal external memory interval management. SIAM Journal on Computing, 32(6):1488-1508, 2003. URL: http://dx.doi.org/10.1137/S009753970240481X.
  6. Jon Louis Bentley. Decomposable searching problems. Information Processing Letters, 8(5):244-251, 1979. URL: http://dx.doi.org/10.1016/0020-0190(79)90117-0.
  7. Gerth Stølting Brodal. External memory three-sided range reporting and top-k queries with sublogarithmic updates. In Proceedings of the 33rd Annual Symposium on Theoretical Aspects of Computer Science (STACS), pages 23:1-23:14, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2016.23.
  8. Timothy M. Chan. Three problems about dynamic convex hulls. International Journal of Computational Geometry and Applications, 22(4):341-364, 2012. URL: http://dx.doi.org/10.1142/S0218195912600096.
  9. Timothy M. Chan, Kasper Green Larsen, and Mihai Pătraşcu. Orthogonal range searching on the RAM, revisited. In Proceedings of the 27th Annual Symposium on Computational Geometry (SoCG), pages 1-10, 2011. URL: http://dx.doi.org/10.1145/1998196.1998198.
  10. Timothy M. Chan and Mihai Pătraşcu. Counting inversions, offline orthogonal range counting, and related problems. In Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 161-173, 2010. URL: http://dx.doi.org/10.1137/1.9781611973075.15.
  11. Bernard Chazelle. A functional approach to data structures and its use in multidimensional searching. SIAM Journal on Computing, 17(3):427-462, 1988. URL: http://dx.doi.org/10.1137/0217026.
  12. Paul F. Dietz. Maintaining order in a linked list. In Proceedings of the 14th Annual ACM Symposium on Theory of Computing (STOC), pages 122-127, 1982. URL: http://dx.doi.org/10.1145/800070.802184.
  13. Otfied Fries, Kurt Mehlhorn, Stefan Näher, and Athanasios K. Tsakalidis. A log log n data structure for three-sided range queries. Information Processing Letters, 25(4):269-273, 1987. URL: http://dx.doi.org/10.1016/0020-0190(87)90174-8.
  14. Vijay Kumar and Eric J. Schwabe. Improved algorithms and data structures for solving graph problems in external memory. In Proceedings of the 8th Annual IEEE Symposium on Parallel and Distributed Processing, pages 169-176, 1996. URL: http://dx.doi.org/10.1109/SPDP.1996.570330.
  15. George S. Lueker. A data structure for orthogonal range queries. In Proceedings of the 19th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 28-34, 1978. URL: http://dx.doi.org/10.1109/SFCS.1978.1.
  16. Edward M. McCreight. Priority search trees. SIAM Journal on Computing, 14(2):257-276, 1985. URL: http://dx.doi.org/10.1137/0214021.
  17. Kurt Mehlhorn and Stefan Näher. Dynamic fractional cascading. Algorithmica, 5(1):215-241, 1990. URL: http://dx.doi.org/10.1007/BF01840386.
  18. Christian Worm Mortensen. Fully-dynamic two dimensional orthogonal range and line segment intersection reporting in logarithmic time. In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 618-627, 2003. URL: http://dl.acm.org/citation.cfm?id=644108.644210".
  19. Christian Worm Mortensen. Fully dynamic orthogonal range reporting on RAM. SIAM Journal on Computing, 35(6):1494-1525, 2006. URL: http://dx.doi.org/10.1137/S0097539703436722.
  20. Yakov Nekrich. Space efficient dynamic orthogonal range reporting. Algorithmica, 49(2):94-108, 2007. URL: http://dx.doi.org/10.1007/s00453-007-9030-9.
  21. Yakov Nekrich. Orthogonal range searching in linear and almost-linear space. Computational Geometry, 42(4):342-351, 2009. URL: http://dx.doi.org/10.1016/j.comgeo.2008.09.001.
  22. Mark H. Overmars. Efficient data structures for range searching on a grid. Journal of Algorithms, 9(2):254-275, 1988. URL: http://dx.doi.org/10.1016/0196-6774(88)90041-7.
  23. Peter van Emde Boas. Preserving order in a forest in less than logarithmic time and linear space. Information Processing Letters, 6(3):80-82, 1977. URL: http://dx.doi.org/10.1016/0020-0190(77)90031-X.
  24. Bryan T. Wilkinson. Amortized bounds for dynamic orthogonal range reporting. In Proceedings of the 22th Annual European Symposium on Algorithms (ESA), pages 842-856, 2014. URL: http://dx.doi.org/10.1007/978-3-662-44777-2_69.
  25. Dan E. Willard. New data structures for orthogonal range queries. SIAM Journal on Computing, 14(1):232-253, 1985. URL: http://dx.doi.org/10.1137/0214019.
  26. Dan E. Willard. Examining computational geometry, Van Emde Boas trees, and hashing from the perspective of the fusion tree. SIAM Journal on Computing, 29(3):1030-1049, 2000. URL: http://dx.doi.org/10.1137/S0097539797322425.
  27. Dan E. Willard and George S. Lueker. Adding range restriction capability to dynamic data structures. Journal of the ACM, 32(3):597-617, 1985. URL: http://dx.doi.org/10.1145/3828.3839.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact