2026-07-23T15:54:51Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11554 2024-03-06T10:48:18Z ddc:004 open_access

External Memory Planar Point Location with Fast Updates Iacono, John Karsin, Ben Koumoutsos, Grigorios point location data structures dynamic algorithms computational geometry We study dynamic planar point location in the External Memory Model or Disk Access Model (DAM). Previous work in this model achieves polylog query and polylog amortized update time. We present a data structure with O(log_B^2 N) query time and O(1/B^(1-epsilon) log_B N) amortized update time, where N is the number of segments, B the block size and epsilon is a small positive constant, under the assumption that all faces have constant size. This is a B^(1-epsilon) factor faster for updates than the fastest previous structure, and brings the cost of insertion and deletion down to subconstant amortized time for reasonable choices of N and B. Our structure solves the problem of vertical ray-shooting queries among a dynamic set of interior-disjoint line segments; this is well-known to solve dynamic planar point location for a connected subdivision of the plane with faces of constant size. Schloss Dagstuhl – Leibniz-Zentrum für Informatik John Iacono and Ben Karsin and Grigorios Koumoutsos 2019 Is Part Of LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2019.58 urn:nbn:de:0030-drops-115548 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.58 eng https://creativecommons.org/licenses/by/3.0/legalcode