Geometric problems are pervasive in many important applications ranging from geographic information systems to physical simulations via the finite element method. The project's basic research concerns the design of efficient scalable parallel algorithms for 1) solving classical geometric problems (e.g. Delaunay triangulation, 3D-Convex hull) and 2) for realizing parallel versions of standard sequential geometric data structures (e.g. kd trees, subdivision hierarchies, quad/oct trees).

Parallel Computational Geometry is concerned with solving geometric problems of size n on parallel computers with p processors (e.g., a PRAM, mesh, or hypercube multiprocessor). Theoretical work in parallel computational geometry has so far focussed on the case n/p=O(1), also referred to as the fine grained case. However, for parallel geometric algorithms to be relevant in practice, such algorithms must be scalable, that is, they must be applicable and efficient for a wide range of ratios n/p.

The focus of this project is on the design of practical scalable algorithms for the coarse grained multicomputer model: p processors, with n/p >> O(1)  local memory each, connected to some arbitrary interconnection network (e.g. mesh, hypercube, fat tree). This abstract model closely matches the architectures of most existing multicomputers (e.g. the Cray T3E, Sunfire, and PC Clusters), while abstracting away for the details of particular interconnection networks, but requires the development of new algorithmic approaches to minimize inter-processor communication by exploiting the locality present in many geometric problems. Results to date indicate that our techniques, based on spatial and data structure partitioning, are very promising in that they are straight-forward to implement and extremely efficient in practice.

Implementation and experimentation are particularly critical in grounding parallel asymptotic results and in demonstrating their applicability in "real world" applications. The applied research component of this project concerns the implementation and evaluation of these parallel algorithms on a range of coarse grained parallel machines.

This project represents ongoing joint work with a number of researchers including Frank Dehne (Carleton), Afonso Ferreira (CRNS France), Laurence Boxer (Niagara), Russ Miller (SUNY USA), and S. Ubeda (France).

Also the following Masters and Ph.D. students in Computer Science have been involved: Albert Chan, M. Diallo and M. Lamoureux.

Publications