Document Open Access Logo

Dynamic Planar Point Location in External Memory

Authors J. Ian Munro, Yakov Nekrich

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2019.52.pdf
  • Filesize: 0.64 MB
  • 15 pages

Document Identifiers

Author Details

J. Ian Munro
  • Cheriton School of Computer Science, University of Waterloo, Canada
Yakov Nekrich
  • Cheriton School of Computer Science, University of Waterloo, Canada

Cite As Get BibTex

J. Ian Munro and Yakov Nekrich. Dynamic Planar Point Location in External Memory. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 52:1-52:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.SoCG.2019.52

Abstract

In this paper we describe a fully-dynamic data structure for the planar point location problem in the external memory model. Our data structure supports queries in O(log_B n(log log_B n)^3)) I/Os and updates in O(log_B n(log log_B n)^2)) amortized I/Os, where n is the number of segments in the subdivision and B is the block size. This is the first dynamic data structure with almost-optimal query cost. For comparison all previously known results for this problem require O(log_B^2 n) I/Os to answer queries. Our result almost matches the best known upper bound in the internal-memory model.

Subject Classification

ACM Subject Classification
  • Theory of computation → Data structures design and analysis
  • Theory of computation
Keywords
  • Data Structures
  • Dynamic Data Structures
  • Planar Point Location
  • External Memory

Metrics

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

Related Versions

References

  1. Pankaj K. Agarwal, Lars Arge, Gerth Stølting Brodal, and Jeffrey Scott Vitter. I/O-efficient dynamic point location in monotone planar subdivisions. In Proc. 10th Annual ACM-SIAM Symposium on Discrete Algorithms, (SODA), pages 11-20, 1999. Google Scholar
  2. Alok Aggarwal and Jeffrey Scott Vitter. The Input/Output Complexity of Sorting and Related Problems. Commun. ACM, 31(9):1116-1127, 1988. URL: http://dx.doi.org/10.1145/48529.48535.
  3. Lars Arge, Gerth Stølting Brodal, and Loukas Georgiadis. Improved dynamic planar point location. In Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, pages 305-314, 2006. URL: http://dx.doi.org/10.1109/FOCS.2006.40.
  4. Lars Arge, Gerth Stølting Brodal, and S. Srinivasa Rao. External Memory Planar Point Location with Logarithmic Updates. Algorithmica, 63(1-2):457-475, 2012. URL: http://dx.doi.org/10.1007/s00453-011-9541-2.
  5. Lars Arge, Andrew Danner, and Sha-Mayn Teh. I/O-efficient point location using persistent B-trees. ACM Journal of Experimental Algorithmics, 8, 2003. URL: http://dx.doi.org/10.1145/996546.996549.
  6. Lars Arge, Vasilis Samoladas, and Jeffrey Scott Vitter. On Two-Dimensional Indexability and Optimal Range Search Indexing. In Proc. 18th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS), pages 346-357, 1999. URL: http://dx.doi.org/10.1145/303976.304010.
  7. Lars Arge and Jan Vahrenhold. I/O-efficient dynamic planar point location. Computational Geometry, 29(2):147-162, 2004. URL: http://dx.doi.org/10.1016/j.comgeo.2003.04.001.
  8. Lars Arge, Darren Erik Vengroff, and Jeffrey Scott Vitter. External-Memory Algorithms for Processing Line Segments in Geographic Information Systems. Algorithmica, 47(1):1-25, 2007. URL: http://dx.doi.org/10.1007/s00453-006-1208-z.
  9. Hanna Baumgarten, Hermann Jung, and Kurt Mehlhorn. Dynamic point location in general subdivisions. J. Algorithms, 17(3):342-380, 1994. URL: http://dx.doi.org/10.1006/jagm.1994.1040.
  10. Samuel W. Bent, Daniel Dominic Sleator, and Robert Endre Tarjan. Biased Search Trees. SIAM J. Comput., 14(3):545-568, 1985. URL: http://dx.doi.org/10.1137/0214041.
  11. Jon Louis Bentley. Algorithms for Klee’s rectangle problems. Unpublished manuscript, Department of Computer Science, Carnegie-Mellon University, 1977. Google Scholar
  12. Gerth Stølting Brodal. External Memory Three-Sided Range Reporting and Top-k Queries with Sublogarithmic Updates. In Proc. 33rd 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.
  13. Timothy M. Chan and Yakov Nekrich. Towards an Optimal Method for Dynamic Planar Point Location. In Proc. 56th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 390-409, 2015. URL: http://dx.doi.org/10.1109/FOCS.2015.31.
  14. Timothy M. Chan and Konstantinos Tsakalidis. Dynamic Planar Orthogonal Point Location in Sublogarithmic Time. In Bettina Speckmann and Csaba D. Tóth, editors, 34th International Symposium on Computational Geometry (SoCG 2018), volume 99 of LIPIcs, pages 25:1-25:15. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018. URL: http://dx.doi.org/10.4230/LIPIcs.SoCG.2018.25.
  15. Bernard Chazelle and Leonidas J. Guibas. Fractional cascading: I. A data structuring technique. Algorithmica, 1(2):133-162, 1986. URL: http://dx.doi.org/10.1007/BF01840440.
  16. Siu-Wing Cheng and Ravi Janardan. New results on dynamic planar point location. SIAM J. Comput., 21(5):972-999, 1992. URL: http://dx.doi.org/10.1137/0221057.
  17. Yi-Jen Chiang, Franco P. Preparata, and Roberto Tamassia. A unified approach to dynamic point location, ray shooting, and shortest paths in planar maps. SIAM J. Comput., 25(1):207-233, 1996. URL: http://dx.doi.org/10.1137/S0097539792224516.
  18. Yi-Jen Chiang and Roberto Tamassia. Dynamization of the trapezoid method for planar point location in monotone subdivisions. Int. J. Comput. Geometry Appl., 2(3):311-333, 1992. URL: http://dx.doi.org/10.1142/S0218195992000184.
  19. Joan Feigenbaum and Robert Endre Tarjan. Two New Kinds of Biased Search Trees. Bell Systems Technical Journal, 62(10):3139-3158, 1983. Google Scholar
  20. Yoav Giora and Haim Kaplan. Optimal dynamic vertical ray shooting in rectilinear planar subdivisions. ACM Transactions on Algorithms, 5(3):28, 2009. URL: http://dx.doi.org/10.1145/1541885.1541889.
  21. Michael T. Goodrich and Roberto Tamassia. Dynamic trees and dynamic point location. SIAM J. Comput., 28(2):612-636, 1998. URL: http://dx.doi.org/10.1137/S0097539793254376.
  22. Michael T. Goodrich, Jyh-Jong Tsay, Darren Erik Vengroff, and Jeffrey Scott Vitter. External-Memory Computational Geometry (Preliminary Version). In Proc. 34th Annual Symposium on Foundations of Computer Science (FOCS), pages 714-723, 1993. URL: http://dx.doi.org/10.1109/SFCS.1993.366816.
  23. Kurt Mehlhorn and Stefan Näher. Dynamic fractional cascading. Algorithmica, 5(2):215-241, 1990. URL: http://dx.doi.org/10.1007/BF01840386.
  24. J. Ian Munro and Yakov Nekrich. Dynamic Planar Point Location in External Memory. CoRR, abs/1903.06601, 2019. URL: http://arxiv.org/abs/1903.06601.
  25. Franco P. Preparata and Roberto Tamassia. Fully dynamic point location in a monotone subdivision. SIAM J. Comput., 18(4):811-830, 1989. URL: http://dx.doi.org/10.1137/0218056.
  26. Franco P. Preparata and Roberto Tamassia. Efficient point location in a convex spatial cell-complex. SIAM J. Comput., 21(2):267-280, 1992. URL: http://dx.doi.org/10.1137/0221020.
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