the sac newsletter
Number 1, November 1996.

Ongoing European Projects in Computer Algebra

The CGAL Esprit BRA Project

CGAL: Computational Geometry Algorithms

by Sabine Stifter

Johannes Kepler University
A-4040 Linz (Austria)

The goal of the project, which has been granted for 18 months, is to develop a library for computational geometry. Starting from geometric data types and data structures, geometric algorithms will be implemented for the most fundamental geometric problems, such as convex hulls, Voronoi diagrams, geometric searching, boolean operations on e.g. polygons, etc. This library will serve as the platform for further development of and experimentation with algorithms within algorithmic geometry for the research community as well as it will be a software package onto which industrial applications within application areas of geometry can be based (such as robotics, CAD/CAM, geographic information systems, image processing and visualization,...).

Althoug computational geometry has developed quited rapidly within the last 15 years, there is no extensive geometric algorithms library available. Only a few attempts by single research groups exist.

CGAL puts ist emphasis not only on sound and efficient algorithms but also on efficient and object oriented programming techniques. In this sense researchers within the field and experienced software developers will cooperate in the project.

Already now, when the project starts, the kernel of the system is ready. The kernel of CGAL has been built from the system LEDA (Saarbruecken), which is so far an extensive library of data types and data structures.

Univ. Utrecht (as leading partner), Univ. Berlin, Univ. Linz, Univ. Saarbruecken, Univ. Tel Aviv, Univ. Zürich, and INRIA in Sophia Antipolis are the participating sites in this project. A utilization committee of about 10 companies working within different areas but all heavily using geometric algorithms within their products, is taking care of early experiments within real applications.