A talk by Mihai Pop
October 9th, 1997. Shaffer 3.
This talk will focus on the design of data structures for answering range queries in a plane. A range query problem requires us to find the set of points lying within a specified rectangle in the plane. Such queries are important in various problems related to geographical databases. This talk will show how one can perform such a query in logarithmic time and linear space, building up on a set of intermediate results. I will focus on the "tricks" used and the analysis of the algorithm at a broad level, without going into the ugly details. If you are not yet excited about algorithms, you'll definitely be after the talk is over.