We present fundamental geometric data structures and algorithms offered by CGAL, the Computational Geometry Algorithms Library. As geometry is ubiquitous this library is used by application developers in medical imaging, VLSI, CAD/CAM, geophysics, computer graphics and last but not least GIS. In this demo we focus on those parts of CGAL which are relevant for geographic information systems software development.

CGAL is a Computational Geometry Algorithms Library written in C++, which is being developed by research groups in Europe and Israel. The goal is to make the large body of geometric algorithms developed in the field of computational geometry available for industrial application. We discuss the major design goals for CGAL, which are correctness, flexibility, ease-of-use, efficiency, and robustness, and present our approach to reach these goals. Generic programming using templates in C++ plays a central role in the architecture of CGAL. We give a short introduction to generic programming in C++, compare it to the object-oriented programming paradigm, and present examples where both paradigms are used effectively in CGAL. Moreover, we give an overview of the current structure of the CGAL-library and consider software engineering aspects in the CGAL-project. Copyright © 2000 John Wiley & Sons, Ltd.

We present a randomized parallel algorithm for constructing the 3D convex hull on a generic p-processor coarse grained multicomputer with arbitrary interconnection network and n/p local memory per pro-Permission to make.digitirl/llarci copies of :111or p:~rt of [his nl:llcri:ll wiLhout fee is granted provided lhat the ct]pics ;Ire II(J1 m:ldc {Jr dis~l-il,~itcd for profit or commercial advantage, the ACM copyrighl/sccvcr notice, the title of the publication and its date appear, and notice is given that copyright is by

Whereas most of the literature assumes that the number of processors p is a function of the problem size n, in scalable algorithms p becomes a parameter of the time complexity. This is a more realistic modelisation of real parallel machines and yields optimal algorithms, for the case that n H p, where H is a function depending on the architecture of the interconnexion network. In this paper we present scalable algorithms for a number of geometric problems, namely lower envelope of line segments, 2D-nearest neighbour, 3D-maxima, 2D-weighted dominance counting area of the union of rectangles, 2D-convex hull. The main idea of these algorithms is to decompose the problem in p subproblems of size 0(F(n;p) + f(p)), with f(p) 2 F(n;p) , which can be solved independently using optimal sequential algorithms. For each problem we present a spatial decomposition scheme based on some geometric observations. The decomposition schemes have in common that they can be computed by globally sorting the entire data set at most twice. The data redundancy of f(p) duplicates of data elements per processor does not increase the asymptotic time complexity and ranges for the algorithms presented in this paper, from p to p2. The algorithms do not depend on a specific architecture,they are easy to implement and in practice efficient as experiments show.