2018/09/27 by Eun‐Jin Oh, Oh, Eunjin
Computer Science · Engineering · #Computational Geometry (cs.CG) #Digital Image Processing Techniques #FOS: Computer and information sciences #Optimization and Packing Problems #Scheduling and Optimization Algorithms
paper · doi:10.48550/arxiv.1809.10495
openalex publication_date 2018/09/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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(nlog n)-space data structure for this problem that supports queries in O(log2 n) time and updates in O(log nloglog n) amortized time. This is the first result that achieves polylogarithmic query and update times simultaneously in incremental (possibly disconnected) 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.