TITLE: Dynamic Planar Range Maxima in Internal and External Memory

Speaker: Konstaninos Tsakalidis, HKUST

Time/Date:  Friday, Nov 9, 11-12
Location: Room 4472

Abstract:

In this talk I'll consider the dynamic two-dimensional maxima/skyline query problem in internal
and external memory. In particular for input size n and output size t, I'll present linear space data
structures that support 3-sided range maxima reporting queries in O(log n + t) and updates in 
O(log n) worst case time in the pointer machine, and in O(log n/loglog n + t) and O(log n/loglog n)
worst case time in the word-RAM model, respectively. Moreover, I'll present an O(n log n) space 
pointer machine data structure that supports 4-sided range maxima reporting queries in O(log^2 n + t)
and updates in O(log^2 n) worst case time. Finally, I'll present a linear space data structure that
supports 3-sided range maxima reporting queries in O(log_{2B^e} n + t/B^{1-e}) I/Os and updates in
O(log_{2B^e} n) I/Os, in the I/O model with block size B.