Effective Computational Geometry for Curves and Surfaces

Shared-cost RTD (FET Open) Project No IST-2000-26473


This project is focused on effectively handling curved objects.


The overall objectives of the project are:
- To take into consideration the multidisciplinary nature of the problem and to develop cooperative research in three main directions: computational geometry, computer algebra and numerical analysis.
- To give Effective Computational Geometry for Curves and Surfaces solid mathematical and algorithmic foundations, to provide solutions to key problems and to validate our theoretical advances through extensive experimental research and the development of software packages that could serve as steps towards a standard for safe and effective geometric computing.
- To promote collaborative research, the interchange between the partners (workshops), exchanges of Ph.D. students and research staff.
- To disseminate our results through research reports, open source softwares, software packages and through a program of open activities including summer-schools and advanced courses intended to academia and industry.

Description of work

Our research will be guided by four different main aspects.

Geometric algorithms for curves and surfaces. We intend to revisit the field of Computational Geometry in order to understand how structures that are well-known for linear objects behave when defined on curves and surfaces.

Algebraic issues. Several operations on nonlinear geometric objects, often lying at the algorithm's bottleneck, are equivalent to manipulating polynomials. A fundamental question is the solution of algebraic systems, ubiquitous in the construction of new objects, such as intersections. Another crucial goal is the implementation of primitives with Boolean or discrete output, such as an object is contained in some bounding object.

Robustness issues. Geometric programs are notorious for their non-robustness: algorithms are designed for a model of computation where real numbers are dealt with exactly and geometric algorithms are frequently only formulated for inputs in general position. This is not simply an academic problem. It is easy to crash any commercial CAD-system. Progress has been made only in recent years. A significant part of the progress was made by the proposers and centers around the so-called exact computation paradigm. We will extend this paradigm to curved objects.

Approximating curves and surfaces. Since algorithms for curves and surfaces are more involved, more difficult to make robust and typically several orders of magnitude slower than their linear counterparts, there is a need for approximate representations. Our objective is to provide robust and quality guaranteed approximations of curves and surfaces.

Milestones and expected results

Deliverables will include publications of results in research reports, conference proceedings and scientific journals.
They will also include prototype implementations, extensive experimental studies and software packages.
The results should be directly useful to various application areas such as computer graphics, geographic information systems, design and manufacturing, robotics, and molecular modeling. Special attention will be paid to the impact of our research, especially in industry.

Participating sites

INRIA Sophia Antipolis - France (coordinator) Prisme/Geometrica and Galaad Groups. Project Manager: Jean-Daniel Boissonnat
Technical Project Manager: Monique Teillaud
ETH Zürich - Switzerland Theory of Combinatorial Algorithms Group Site leader: Emo Welzl
Freie Universität Berlin - Germany Group Theoretical Computer Science Site leader: Günter Rote
Rijksuniversiteit Groningen - Netherlands High-Performance Computing and Imaging Group Site leader: Gert Vegter
MPI Saarbrücken - Germany Algorithms and Complexity Group Site leader: Kurt Mehlhorn
Tel Aviv University - Israel School of Computer Science Site leader: Dan Halperin


This work is partially supported by the IST Programme of the European Union.
Total cost:1 595 600 EUR
Community funding:1 029 000 EUR
Project start:May 1st 2001
Duration:36 months
IST home
FET Home

Coordinator contact details

Jean-Daniel Boissonnat
INRIA, BP 93, 06902 Sophia Antipolis, FRANCE          <Jean-Daniel.Boissonnat@sophia.inria.fr>
Last modified: Fri Nov 24 10:29:17 CET 2006