2026-07-20T05:09:42Z https://drops.dagstuhl.de/oai

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

Point Location in Incremental Planar Subdivisions Oh, Eunjin Dynamic point location general incremental planar subdivisions We study the point location problem in incremental (possibly disconnected) planar subdivisions, that is, dynamic subdivisions allowing insertions of edges and vertices only. Specifically, we present an O(n log n)-space data structure for this problem that supports queries in O(log^2 n) time and updates in O(log n log log n) amortized time. This is the first result that achieves polylogarithmic query and update times simultaneously in incremental planar subdivisions. Its update time is significantly faster than the update time of the best known data structure for fully-dynamic (possibly disconnected) planar subdivisions. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Eunjin Oh 2018 Is Part Of LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2018.51 urn:nbn:de:0030-drops-99991 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.51 eng https://creativecommons.org/licenses/by/3.0/legalcode