Geometric Range Searching

Jiri Matousek Department of Computer Science Charles University, CSFR Report B 93-09 July 93

Get the report here here or by anonymous ftp: 
File:   pub/reports/
In geometric range searching, algorithmic problems of the following type are considered: Given an $n$-point set $P$ in the plane, build a data structure so that, given a query triangle $R$, the number of points of $P$ lying in $R$ can be determined quickly. We present a survey of results and main techniques in this area.