Theory Seminar: Sariel Har-Peled, "Orthogonal Emptiness Queries for Random Points"
- Event Type
- Seminar/Symposium
- Sponsor
- Michael A. Forbes
- Location
- Siebel 3401
- Date
- Mar 3, 2025 11:00 am
- Speaker
- Sariel Har-Peled
- Views
- 101
- Originating Calendar
- Siebel School Speakers Calendar
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].