(image by Manuel Caroli - click on the image to see a larger version)


Triangulations and meshes in new spaces

INRIA Program "Associate Teams"
Starting date: January 1st, 2009.
Duration: 3 years.
(Unfortunately, INRIA does not support associate teams within Europe any more...)
accès restreint INRIA:
proposition initiale
demande de prolongation en 2010
demande de prolongation en 2011



Geometrica project-team
INRIA Sophia Antipolis - Méditerranée
Coordinator: Monique Teillaud
Institute of Mathematics and Computing Science
Kapteyn Astronomical Institute
University of Groningen
Coordinator: Gert Vegter
Rien van de Weijgaert

[Scientific Objectives] - [Workshops] - [Visits] - [Results]

Scientific Objectives

Due to the now established emergence of standardized software libraries, such as the Computational Geometry Algorithms Library CGAL, a result of concerted efforts by groups of researchers in Europe, and whose Geometrica is one of the leaders, the so-far mostly theoretical results developed in computational geometry are being used and extended for practical use like never before for the benefit of researchers in academia and of industry.
To fulfill the promise of applicability of computational geometry and to expand the scope of initial efforts, extending the traditional focus on the Euclidean space Rd ("urbi") to encompass various spaces ("orbi") has become important and timely.

Motivation - Applications
This research was originally motivated by the needs of astronomers in Groningen who study the evolution of the large scale mass distribution in our universe by running dynamical simulations on periodic 3D data.
In fact there are numerous application fields needing robust software for geometric problems in non-Euclidean spaces, in particular periodic spaces. A small sample of these needs, in fields like astronomy, material engineering for prosthesis, mechanics of granular materials, was presented at the CGAL Prospective Workshop on Geometric Computing in Periodic Spaces. Many other diverse application fields could be mentioned, for instance biomedical computing, solid-state chemistry, modeling of foams, physics of condensed matter, fluid dynamics, this list being very far from exhaustive.

Our goals are
(i) the design of algorithms relying on strong theoretical studies guaranteeing the validity of the computed structures;
(ii) the production of efficient and robust software to be integrated into CGAL, implementing these algorithms;
(iii) using our software to run experiments on real data.

Geometric structures
We will study various related problems such as computing Delaunay triangulations, alpha-shapes, meshes, Betti numbers, that are motivated by application domains.
Let us mention that though this is not emphasized in this text, we will try to obtain results in all dimensions, even if we first focus on 2D and 3D spaces.
The most fundamental question will be the computation of the Delaunay triangulation of a set of points, since the computation of meshes is often based on this Delaunay triangulation.


A first class of spaces that should be considered consists of orbifolds, that are quotient spaces under some discrete subgroup of motions acting on a Euclidean or non-Euclidean space, like periodic spaces (e.g., tori, cylinders, that are 2D Euclidean orbifolds, i.e. quotients of Euclidean 2-space), projective space (a quotient of the sphere), or surfaces of higher genus (quotients of the hyperbolic plane).

Preliminary results have been obtained in these two cases.

It must be noted that the Delaunay triangulation of the flat torus mentioned above is computed in the space of parameters [0,1)3and does not take into account the intrinsic metric of the torus considered as a 3D hypersurface in 4D. This is fine for most applications (simulations mentioned above). But it is interesting for some applications to see whether the triangulation could be later deformed to adapt to this intrinsinc metric.
The same question holds for the hyperbolic case.

Other spaces, like C2, the space of quaternions (used to represent rotations), the spaces of lines or line segments, offer a wide variety of questions and applications in a longer term perspective.



October 19-27, 2009 Rien van de Weijgaert visits INRIA.
He gives a talk: Morphology and Structure of the Cosmic Web: Tesselation-based Analysis.
October 20-30, 2009 Gert Vegter visits INRIA.
November 9-15, 2009 Manuel Caroli and Monique Teillaud visit U. Groningen.
November 16-20, 2009 Julie Bernauer, Manuel Caroli, Frédéric Chazal, Michael Hemmer, Quentin Mérigot, and Monique Teillaud (INRIA)
Jakob van Bethlehem, Patrick Bos, Amit Chattopadhyay, Bernard Jones, Erwin Platen, Pratyush Pranav, Fatma Senguler-Ciftci, Esra Tigrak, Gert Vegter, and Rien van de Weijgaert (Groningen)
attend the workshop in Leiden
November 21-27, 2009 Manuel Caroli and Monique Teillaud visit U. Groningen.
January 25 - February 7, 2010    Gert Vegter visits INRIA.
He gives a talk: Complexity of curve approximation.
May 3-28, 2010    Manuel Caroli visits U. Groningen.
May 19-28, 2010    Monique Teillaud visits U. Groningen.
June 6-23, 2010    Pratyush Pranav visits INRIA.
October 18-31, 2010    Gert Vegter visits INRIA.
December 1-10, 2010   
December 6-10, 2010   
Rien van de Weijgaert visits INRIA.
Gert Vegter and Johan Hidding visit INRIA.
Gert Vegter and Rien van de Weijgaert give talks at the workshop.
Gert Vegter is a member of the PhD defense committee of Manuel Caroli.
May 9-21, 2011    Monique Teillaud visits U. Groningen.
May 9-31, 2011    Mikhail Bogdanov visits U. Groningen.
October 4-23, 2011    Gert Vegter visits INRIA.
October 4-15, 2011    Rien van de Weijgaert visits INRIA.
October 6-15, 2011    Pratyush Pranav and Mathijs Wintraecken visit INRIA.
December 5-13, 2011    Monique Teillaud visits U. Groningen.

After the end of OrbiCG, the collaboration continues, albeit on a smaller scale.
October 8-20, 2012    Gert Vegter visits INRIA.


After the end of OrbiCG, the collaboration continues, albeit on a smaller scale.

Monique Teillaud