
Project
Overview
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, 3DConvex 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 interprocessor 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 straightforward to implement and
extremely efficient in practice.


Publications
Papers
in Refereed Journals 
A. Ferreira, I. Guerin Lassous, K. Marcus, and A. RauChaplin,
"Parallel computation on interval graphs: algorithms and experiments"
, Concurrency and Computation: Practice and Experience, Volume 14, Number 11, Aug 2002, pages 885910. 
M. Diallo, A. Ferreira, A. RauChaplin,
"A Note On CommunicationEfficient Deterministic Parallel Algorithms for Planar Point Location and 2d Voronoi Diagram"
, Parallel Processing Letters, Volume 11, Number 23, Sep 2001, pages 327340. 
L. Boxer, Russ Miller, Andrew RauChaplin,
"Scaleable Parallel Algorithms for Geometric Pattern Recognition"
, Journal of Parallel and Distributed Computing, Volume 58, Number 3, Sep 1999, pages 466486. 
A. Ferreira, C. Kenyon, A. RauChaplin, and S. Ubeda,
"Scalable Algorithms for the dDimensional Range Search on Coarse Grained Multicomputers"
, ALGORITHMICA (Special Issue on Coarse Grained Parallel Algorithms), Volume 24, Number 3/4, Jul 1999, pages 195208. 
A. Chan, F. Dehne, and A. RauChaplin,
"Coarse Grained Parallel Geometric Search"
, Journal of Parallel and Distributed Computing, Volume 57, Number 2, May 1999, pages 224236. 
M. Diallo, A. Ferreira, A. RauChaplin, and S. Ubeda,
"Scalable 2d convex hull and triangulation algorithms for coarse grained multicomputers"
, Journal of Parallel and Distributed Computing, Volume 56, Number 1, Jan 1999, pages 4770. 
L. Boxer, R. Miller, A. RauChaplin,
"Scaleable Parallel Algorithms for Lower Envelopes with Applications"
, Journal of Parallel and Distributed Computing, Volume 53, Number 2, Sep 1998, pages 91118. 
F. Dehne, A. Fabri, and A. RauChaplin,
"Scalable Parallel Geometric Algorithms for Multicomputers"
, International Journal of Computational Geometry and Applications, Volume 6, Jan 1996, pages 379400. 
Papers
in Refereed Conference Proceedings 
A. CosgayaLozano, A. RauChaplin, and N. Zeh,
"Parallel Computation of Skyline Queries"
in Proceedings of the 21th International Symposium on High Performance Computing Systems and Applications (HPCS'07), Saskatoon, Canada, May 2007. 
F. Dehne, T. Eavis, and A. RauChaplin,
"Querying ROLAP cubes in the presence of hierarchies"
in Proceedings of the 8th International Workshop on Data Warehousing and OLAP, ACM, pages 8996, Bremen, Germany, Nov 2005. 
A. Chan, C. Gao, and A. RauChaplin,
"A Coarse Grained Parallel Algorithm for Closest Larger Ancestors In Trees with Applications to Single Link Clustering"
in Proceedings of the International Conference on High Performance Computing and Communications (HPCC05), Italy, May 2005. 
M. Lamoureux and A. RauChaplin,
"Parallel Algorithms for Grounded Range Search and Applications"
in Proceedings of Europar'99, Volume 1685, Lecture Notes in Computer Science, pages 525532, Toulouse, France, Aug 1999. 
A. Ferreira, I. Guerin Lassous, K. Marcus, and A. RauChaplin,
"Parallel computation on interval graphs using pc clusters: Algorithms and experiments"
in Proceedings of Europar'98 (Distinguished Paper), Volume 1470, Lecture Notes in Computer Science, Springer Verlag, pages 875886, Southampton, UK, Sep 1998. 
M. Diallo, A. Ferreira, A. RauChaplin,
"CommunicationEfficient Deterministic Parallel Algorithms for Planar Point Location and 2d Voronoi Diagram"
in Proceedings of the 15th Symposium on Theoretical Aspects of Computer Science (STACS '98), Volume 1373, Lecture Notes in Computer Science, Springer Verlag, pages 399409, Paris, France, Feb 1998. 
A. Ferreira, C. Kenyon, A. RauChaplin, and S. Ubeda,
"Scalable Algorithms for the dDimensional Range Search on Coarse Grained Multicomputers"
in Proceedings of the 11th International Parallel Processing Symposium (IPPS'97), pages 616620, Apr 1997. 
A. Chan, F. Dehne, and A. RauChaplin,
"Coarse Grained Parallel Geometric Search"
in Proceedings of the 11th International Parallel Processing Symposium (IPPS'97), pages 320325, Apr 1997. 
R. Miller, L. Boxer, and A. RauChaplin,
"Some Scalable Parallel Algorithms for Geometric Problems"
in Proceedings of the 8th IASTED International Conference on Parallel and Distributed Computing Systems (PDCS'96), pages 426430, Oct 1996. 
A. RauChaplin,
"Scalable Algorithm Design Techniques for Discrete Problems that Lack Obvious Structure"
in Proceedings of the of International Symposium on Parallel Computing for Solving Large Scale Irregular Applications (Stratagem'96), pages 515, Nice, France, Jul 1996. 
A. Ferreira, A. RauChaplin, and S. Ubeda,
"Scalable 2d convex hull and triangulation algorithms for coarse grained multicomputers"
in Proceedings of the 7th IEEE Symposium on Parallel and Distributed Processing (SPDP'95), pages 561568, Jan 1995. 
F. Dehne, A. Fabri, and A. RauChaplin,
"Scalable Parallel Geometric Algorithms for Multicomputers"
in Proceedings of the ACM Symposium on Computational Geometry, IEEE Press, pages 298307, Jan 1993. 
