Document Open Access Logo

Dynamic Planar Orthogonal Point Location in Sublogarithmic Time

Authors Timothy M. Chan, Konstantinos Tsakalidis

PDF

File

Thumbnail PDF
PDF
LIPIcs.SoCG.2018.25.pdf
  • Filesize: 433 kB
  • 15 pages

Document Identifiers

Subject Classification

Keywords
  • dynamic data structures
  • point location
  • word RAM

Metrics

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

Abstract

We study a longstanding problem in computational geometry: dynamic 2-d orthogonal point location, i.e., vertical ray shooting among n horizontal line segments. We present a data structure achieving O(log n / log log n) optimal expected query time and O(log^{1/2+epsilon} n) update time (amortized) in the word-RAM model for any constant epsilon>0, under the assumption that the x-coordinates are integers bounded polynomially in n. This substantially improves previous results of Giyora and Kaplan [SODA 2007] and Blelloch [SODA 2008] with O(log n) query and update time, and of Nekrich (2010) with O(log n / log log n) query time and O(log^{1+epsilon} n) update time. Our result matches the best known upper bound for simpler problems such as dynamic 2-d dominance range searching.
We also obtain similar bounds for orthogonal line segment intersection reporting queries, vertical ray stabbing, and vertical stabbing-max, improving previous bounds, respectively, of Blelloch [SODA 2008] and Mortensen [SODA 2003], of Tao (2014), and of Agarwal, Arge, and Yi [SODA 2005] and Nekrich [ISAAC 2011].

Cite As Get BibTex

Timothy M. Chan and Konstantinos Tsakalidis. Dynamic Planar Orthogonal Point Location in Sublogarithmic Time. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 25:1-25:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.SoCG.2018.25

Author Details

Timothy M. Chan
Konstantinos Tsakalidis

References

  1. Pankaj K. Agarwal, Lars Arge, Haim Kaplan, Eyal Molad, Robert E. Tarjan, and Ke Yi. An optimal dynamic data structure for stabbing-semigroup queries. SIAM Journal on Computing, 41(1):104-127, 2012. Preliminary version in SODA 2005. URL: http://dx.doi.org/10.1137/10078791X.
  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, 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), 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. Guy E. Blelloch. Space-efficient dynamic orthogonal point location, segment intersection, and range reporting. In Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 894-903, 2008. URL: http://dl.acm.org/citation.cfm?id=1347082.1347180.
  7. Timothy M. Chan. Geometric applications of a randomized optimization technique. Discrete & Computational Geometry, 22(4):547-567, 1999. URL: http://dx.doi.org/10.1007/PL00009478.
  8. Timothy M. Chan. Persistent predecessor search and orthogonal point location on the word RAM. ACM Transactions on Algorithms, 9(3):22:1-22:22, 2013. Preliminary version in SODA 2011. URL: http://dx.doi.org/10.1145/2483699.2483702.
  9. Timothy M. Chan and Yakov Nekrich. Towards an optimal method for dynamic planar point location. In Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 390-409, 2015. URL: http://dx.doi.org/10.1109/FOCS.2015.31.
  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. Timothy M. Chan and Dimitrios Skrepetos. All-pairs shortest paths in unit-disk graphs in slightly subquadratic time. In Proceedings of the 27th International Symposium on Algorithms and Computation (ISAAC), pages 24:1-24:13, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.ISAAC.2016.24.
  12. Timothy M. Chan and Konstantinos Tsakalidis. Dynamic orthogonal range searching on the RAM, revisited. In Proceedings of the 33rd International Symposium on Computational Geometry (SoCG), pages 28:1-28:13, 2017. URL: http://dx.doi.org/10.4230/LIPIcs.SoCG.2017.28.
  13. Richard Cole and Ramesh Hariharan. Dynamic LCA queries on trees. SIAM Journal on Computing, 34(4):894-923, 2005. URL: http://dx.doi.org/10.1137/S0097539700370539.
  14. Paul F. Dietz. Fully persistent arrays. In Proceedings of the 1st Workshop for Algorithms and Data Structures (WADS), pages 67-74, 1989. URL: http://dx.doi.org/10.1007/3-540-51542-9_8.
  15. Michael Fredman and Michael Saks. The cell probe complexity of dynamic data structures. In Proceedings of the 21st Annual ACM Symposium on Theory of Computing (STOC), pages 345-354, 1989. URL: http://dx.doi.org/10.1145/73007.73040.
  16. Yoav Giyora and Haim Kaplan. Optimal dynamic vertical ray shooting in rectilinear planar subdivisions. ACM Transactions on Algorithms, 5(3):28:1-28:51, 2009. Preliminary version in SODA 2007. URL: http://dx.doi.org/10.1145/1541885.1541889.
  17. Katherine Jane Lai. Complexity of union-split-find problems. Master’s thesis, MIT, 2008. URL: http://hdl.handle.net/1721.1/45638.
  18. Kurt Mehlhorn and Stefan Näher. Dynamic fractional cascading. Algorithmica, 5(1):215-241, 1990. URL: http://dx.doi.org/10.1007/BF01840386.
  19. 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.
  20. Christian Worm Mortensen. Data structures for orthogonal intersection searching and other problems. PhD thesis, IT University of Copenhagen, 2006. URL: http://www.epust.dk/main.pdf?attredirects=0.
  21. 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.
  22. Christian Worm Mortensen, Rasmus Pagh, and Mihai Pǎtraşcu. On dynamic range reporting in one dimension. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC), pages 104-111, 2005. URL: http://dx.doi.org/10.1145/1060590.1060606.
  23. Yakov Nekrich. Searching in dynamic catalogs on a tree. CoRR, abs/1007.3415, 2010. URL: http://arxiv.org/abs/1007.3415.
  24. Yakov Nekrich. A dynamic stabbing-max data structure with sub-logarithmic query time. In Proceedings of the 22nd International Symposium on Algorithms and Computation (ISAAC), pages 170-179, 2011. URL: http://dx.doi.org/10.1007/978-3-642-25591-5_19.
  25. Mark H. Overmars. The Design of Dynamic Data Structures, volume 156 of Lecture Notes in Computer Science. Springer, 1983. URL: http://dx.doi.org/10.1007/BFb0014927.
  26. Yufei Tao. Dynamic ray stabbing. ACM Transactions on Algorithms, 11(2):11:1-11:19, 2014. URL: http://dx.doi.org/10.1145/2559153.
  27. 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.
  28. Peter van Emde Boas, Robert Kaas, and Erik Zijlstra. Design and implementation of an efficient priority queue. Mathematical Systems Theory, 10(1):99-127, 1976. Google Scholar
  29. Bryan T. Wilkinson. Amortized bounds for dynamic orthogonal range reporting. In Proceedings of the 22nd Annual European Symposium on Algorithms (ESA), pages 842-856, 2014. URL: http://dx.doi.org/10.1007/978-3-662-44777-2_69.
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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact