(image by Manuel Caroli - click on the image to see a larger version) |
OrbiCGTriangulations and meshes in new spacesINRIA 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 |
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 R^{d} ("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.
Goals
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.
Spaces
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)^{3}and 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 C^{2}, 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.
2009 | |
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. |
2010 | |
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. |
2011 | |
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.
2012 | |
October 8-20, 2012 | Gert Vegter visits INRIA. |