Theory Seminar: Please join us on March 3rd, at 11am in Siebel 3401 where Sariel Har-Peled will give a talk, “Orthogonal Emptiness Queries for Random Points”. Please see the abstract below:
Abstract: We present a new data-structure for orthogonal range searching for random points in the plane. In particular, the new data-structure has (expected) size $O(n \log n ( \log \log n)^2 )$, and answers queries in constant time. As a building block, we construct a data-structure, of expected linear size, that answers predecessor queries in constant time, for random numbers sampled uniformly from [0,1].