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: 
Server: fubinf.inf.fu-berlin.de
File:   pub/reports/tr-b-93-09.ps.gz

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.

Geometric Range Searching

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