2026-07-23T13:24:22Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10456 2024-03-06T10:46:02Z ddc:004 open_access

Dynamic Planar Point Location in External Memory Munro, J. Ian Nekrich, Yakov Data Structures Dynamic Data Structures Planar Point Location External Memory 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik J. Ian Munro and Yakov Nekrich 2019 Is Part Of LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2019.52 urn:nbn:de:0030-drops-104566 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.52 eng https://creativecommons.org/licenses/by/3.0/legalcode