Seminar • Algorithms and Complexity — Dynamic Planar Point Location in External Memory

Yakov Nekrich, Department of Computer Science
Michigan Technological University

We describe a fully-dynamic data structure for the planar point location problem in the external memory model. Our data structure supports queries in O(logBn(loglogBn)3)) I/Os and updates in O(logBn(loglogBn)2)) amortized I/Os, where n is the number of segments in the subdivision and B is the block size. This is the first dynamic data structure with almost-optimal query cost. For comparison all previously known results for this problem require O(log2Bn) I/Os to answer queries. Our result almost matches the best known upper bound in the internal-memory model. 

Joint work with Ian Munro.