(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:
demande de prolongation en 2010
demande de prolongation en 2011
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
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
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.
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).
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
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
|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.|