I/O-efficient dynamic planar point location (extended abstract)
Lars Arge, Jan Vahrenhold · 2000
We present the first provably I/O-efficient dynamic data structure for point location in a general planar subdivision.Our structure uses O(N/B) disk blocks to store a subdivision of size N, where B is the disk block size.Queries can be answered in 0(log~ N) I/Os in the worst-case, and insertions and deletions can be performed in O(log 2 N) and O(10g B N) I/Os amortized, respectively.Previously, an I/Oefficient dynamic point location structure was only known for monotone subdivisions.Part of our data structure is based on a new external version of the so-called logarithmic method which allows for efficient dynamization of static external-memory data structures with certain characteristics.We believe that this method could prove helpful in the dynamization of other external memory structures.