External Memory Planar Point Location with Logarithmic Updates

Point location is an extremely well‐studied problem both in internal memory models and recently also in the external memory model. In this paper, we present an I/O‐efficient dynamic data structure for point location in general planar subdivisions. Our structure uses linear space to store a subdivision with N segments. Insertions and deletions of segments can be performed in amortized O(log B N) I/Os and queries can be answered in $O({\log }_B^{2}N)$ I/Os in the worst‐case. The previous best known linear space dynamic structure also answers queries in $O({\log }_B^{2}N)$ I/Os, but only supports insertions in amortized $O({\log }_B^{2}N)$ I/Os. Our structure is also considerably simpler than previous structures.