External memory planar point location with logarithmic updates (Q5920252): Difference between revisions

The authors of this paper describe a linear-space external-memory data structure for dynamic planar point location. In the external-memory model we have an internal memory that can hold \(M\) elements (edges or vertices), in which we can perform computations for free, and an unbounded external memory for storage; we can transfer a block of \(B \leq M / 2\) elements between internal and external memories at the cost of one input or output (I/O). The authors' data structure uses \(O (N / B)\) blocks to store a set of \(N\) line segments that divide the plane into faces, such that we can determine which face contains any given query point using \(O (\log_B^2 N)\) I/Os in the worst case, and insert or delete a line segment using \(O (\log_B N)\) amortized I/Os. The best previous solution was due to \textit{L. Arge} and \textit{J. Vahrenhold} [Comput. Geom. 29, No. 2, 147--162 (2004; Zbl 1056.68062)] and it also used \(O (N / B)\) blocks, \(O (\log_B^2 N)\) I/Os for queries in the worst case and \(O (\log_B N)\) amortized I/Os for deletion, but was more complicated and used \(O (\log_B^2 N)\) amortized I/Os for insertion.