GEOMETRICA Research team

Geometric computing

Team presentation

Geometric computing plays a central role in most engineering activities: geometric modelling, computer aided design and manufacturing, computer graphics and virtual reality, scientific visualization, geographic information systems, molecular biology, fluid mechanics, and robotics are just a few well-known examples. The rapid advances in visualization systems, networking facilities and 3D sensing and imaging make geometric computing both dominant and more demanding of effective algorithmic solutions.

Computational geometry emerged as a discipline in the seventies and has met with considerable success in resolving the asymptotic complexity of basic geometric problems including data structures, convex hulls, triangulations, Voronoi diagrams, geometric arrangements and geometric optimisation. However, in the mid-nineties, it has been recognized that the applicability in practice of the computational geometry techniques was far from satisfactory and a vigorous effort has been undertaken to make computational geometry more effective.

Together with partners in Europe, the former PRISME project-team advanced the state of the art in robustness issues, geometric software engineering and experimental studies. A major outcome of this research has been the development of a large library of computational geometry algorithms (CGAL).

GEOMETRICA aims at pursuing further the effort of the PRISME project-team. Its focus is on effective computational geometry for Curves and Surfaces. This is a challenging research area with a huge number of potential applications in almost all application domains involving geometric computing. GEOMETRICA is primarily working in geometric modeling with applications in graphics, medecine and structural biology, meshes for scientific computing, telecommunications and transmission of geometric data.

Research themes

The research program follows three main directions:

Conception and analysis of geometric data structures and algorithms, robust computation and advanced programming, shape approximation, meshing and compression.

Geometric data structures and algorithms: one goal of the project is to develop Computational Geometry for curved objects. In particular, we work on non affine Voronoi diagrams that are encountered in geometric optimization, structural biology and mesh generation.

Robust computation and advanced programming: software design, numerical stability and practical efficiency are major issues. We work on effective exact computing, dedicated arithmetics and fixed-precision geometric constructions. GEOMETRICA is one of the groups leading the development of the CGAL library. CGAL is both a basis for further research in Computational Geometry and a platform to disseminate research results.

Shape approximation. Complex shapes are ubiquitous in numerical analysis, computer graphics, robotics and many other fields. In most cases, they need to be approximated, with various needs and constraints though. Conversely, surface reconstruction requires to interpolate shapes from samples. GEOMETRICA aims at developing a theory of geometric approximation and works on sampling, discrete differential geometry, approximations with topological and geometrical guarantees, multi-scale representation. GEOMETRICA works also on compression and progressive transmission of geometric models.

International and industrial relations

The closest collaborations of the project-team GEOMETRICA --formerly Prisme-- are with the best European teams active in Computational Geometry. These collaborations have been developed throughout several European projects focusing on Algorithms and Computational Geometry.

The GeometryFactory, a start-up company was launched to commercialize the CGAL library.

Keywords: Algorithms and data structures Robust computation Approximation and mesh generation

Research teams of the same theme :

Inria Headquarters and research centres

Direct links

Social