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(frac{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.
Download