Overview

Transforming a geometric algorithm into an effective computer program is a difficult task. This transformation is made particularly hard by the basic assumptions of most theoretical geometric algorithms concerning complexity measures and (more crucially) the handling of robustness issues. The paper starts with a discussion of the gap between the theory and practice of geometric algorithms, together with a brief review of existing solutions to some of the problems that this dichotomy brings about.

We then turn to an overview of the Cgal project and library. The Cgal project is a joint effort by a number of research groups in Europe and Israel to produce a robust software library of geometric algorithms and data structures. The library is now available for use with significant functionality. We describe the main goals and results of the project.

The central part of the paper is devoted to arrangements (i.e., space subdivisions induced by geometric objects) and motion planning. We concentrate on the maps and arrangements part of the Cgal library. Then we describe two packages developed on top of Cgal for constructing robust geometric primitives for motion algorithms.

1 Introduction

For over two decades, research in Computational Geometry has yielded numerous efficient algorithms and data structures for solving problems arising in a diversity of areas from statistics and chemistry to GIS and robotics [42],[54],[68]. Whereas the original focus of this field was almost exclusively theoretical, these days a lot of attention is given to practical...