Sponsor: NSF
This project investigates the design of parallel algorithms for geometric problems, both for shared-memory (PRAM) models and the (more realistic) network models. Within the network models, the investigation will focus on the situation where the number of processors available 
is fixed (i.e., does not depend on the size 
of the problem being solved).
In such a framework, one often needs to bring into the picture the sequential "front end" to the parallel machine, since the parallel machine may be too small to even store the problem being solved. Thus, the techniques used are both parallel and sequential, since a substantial part of the computation may take place in the sequential front-end machine, or even sequentially within each processor if each processor has a substantial amount of local memory (the "coarse grain" case). Also of interest are problems that are still open within the traditional frameworks (i.e., assuming massive rather than limited parallelism), with special emphasis on problems whose solution would impact the parallel complexity of many geometric problems (for example, multisearching and matrix searching).