Dynamic 3-sided Planar Range Queries with Expected Doubly Logarithmic   Time
  This work studies the problem of 2-dimensional searching for the 3-sided range query of the form $[a, b]\times (-\infty, c]$ in both main and external memory, by considering a variety of input distributions. We present three sets of solutions each of which examines the 3-sided problem in both RAM and I/O model respectively. The presented data structures are deterministic and the expectation is with respect to the input distribution. 
Gerth St{\o}lting Brodal, Alexis C. Kaporis, Apostolos N.   Papadopoulos, Spyros Sioutas, Konstantinos Tsakalidis, Kostas Ts...
cs.DS