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(logBN) I/Os and queries can be answered in O(logB2N) I/Os in the worst-case. The previous best known linear space dynamic structure also answers queries in O(logB2N) I/Os, but only supports insertions in amortized O(logB2N) I/Os. Our structure is also considerably simpler than previous structures.
Original language
English
Title of host publication
Proceedings of the twenty-fourth annual symposium on Computational geometry