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

OrbiCG 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 Intranet

Partners

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 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).

• As previously mentioned, working in the 3D flat torus has numerous applications, so, this space will deserve a particular attention. Our contacts with researchers in various application fields will allow us to determine which other Euclidean periodic spaces (such as cylinders, that are quotients of other Euclidean space) should be studied.
• The projective spaces P^d, when d is even, raise a problem of different nature, since they are not oriented, while standard algorithms for computing triangulations in R^d intensively rely on orientation tests. We expect the case of projective spaces to have application in fields like computer vision. More generally, CGAL does not offer any functionality in the projective case, it would be beneficial to remove this restriction.

• Concerning surfaces of higher genus, first we need to develop a criterion to detect whether point sets on hyperbolic surfaces admit a Delaunay triangulation (defined with regard to the hyperbolic metric, e.g., in the Poincaré disk or half-plane model).
  Then we need to develop an algorithm computing the Delaunay triangulation of such point sets; It is not completely clear whether, and how, existing algorithms can be generalized to non-Euclidean geometries.

It must be noted that the Delaunay triangulation of the flat torus mentioned above is computed in the space of parameters [0,1)³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², 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.

Workshops

• Subdivide and Tile: Triangulating spaces for understanding the world, 16-20 Nov 2009, Lorentz Center, Leiden, The Netherlands.
• OrbiCG/Triangles Workshop on Computational Geometry , 8-10 Dec 2010, INRIA Sophia Antipolis - Méditerranée, France.

Visits

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

2012
October 8-20, 2012	Gert Vegter visits INRIA.

Results

• Mark Abspoel. Computing homology of subcomplexes of the 3-torus. BSc thesis university of Groningen, August 2009. Supervisor: Gert Vegter.
• Manuel Caroli and Monique Teillaud. Computing 3D Periodic Triangulations. In Proceedings 17th European Symposium on Algorithms, volume 5757 of Lecture Notes in Computer Science, pages 37-48, 2009. Full version Research Report 6823, INRIA, 2009.
• Manuel Caroli and Monique Teillaud.3D Periodic Triangulations. In CGAL Editorial Board, editor, CGAL User and Reference Manual. 3.5 and 3.6 edition, 2009 and 2010.
• Manuel Caroli and Monique Teillaud. Delaunay Triangulations of Point Sets in Closed Euclidean d-Manifolds. In Abstracts 26th European Workshop on Computational Geometry, pages 101-104, 2010. Full version: Research Report 7352, INRIA, 2010.
• Manuel Caroli, Pedro M. M. de Castro, Sébastien Loriot, Olivier Rouiller, Monique Teillaud, and Camille Wormser. Robust and Efficient Delaunay Triangulations of Points on or Close to a Sphere. In 9th International Symposium on Experimental Algorithms, volume 6049 of Lecture Notes in Computer Science, pages 462-473, 2010.
• R. van de Weygaert, E. Platen, G. Vegter, B. Eldering and N. Kruithof. Alpha Shape Topology of the Cosmic Web. Seventh International Symposium on Voronoi Diagrams in Science and Engineering, Quebec City, CA, pag. 224-234, June 28-30, 2010.
• Manuel Caroli, Vissarion Fisikopoulos, and Monique Teillaud. Meshing of Triply-Periodic Surfaces in CGAL. In Seventh International Conference on Curves and Surfaces, 2010. Note: Poster presentation.
• J. Hidding, Adhesion: a sticky way of understanding large scale structure. MSc thesis University of Groningen, July 2010. Supervisor: R. van de Weygaert
• G.F.E. Senden, The topology of the Universe. BSc thesis university of Groningen, August 2010. Supervisors: G. Vegter and M. de Roo.
• E. Platen, R. van de Weygaert, M. Aragon-Calvo, B.J.T. Jones and G. Vegter: Structural Analysis of the SDSS Cosmic Web I. Nonlinear Density Field Reconstruction, MNRAS, 2011.
• Manuel Caroli, Triangulations of Orbit Spaces. PhD thesis. University of Nice, December 2010. Advisor: Monique Teillaud.
• Manuel Caroli and Monique Teillaud. Delaunay Triangulations of Point Sets in Closed Euclidean d-Manifolds. In Proceedings 27th Annual Symposium on Computational Geometry, 2011.
• Rien van de Weygaert, Gert Vegter, Herbert Edelsbrunner, Bernard J.T. Jones, Pratyush Pranav, Changbom Park, Wojciech A. Hellwing, Bob Eldering, Nico Kruithof, E.G.P. (Patrick) Bos, Johan Hidding, Job Feldbrugge, Eline ten Have, Matti van Engelen, Manuel Caroli, and Monique Teillaud. Alpha, Betti and the Megaparsec Universe: on the Homology and Topology of the Cosmic Web. In Transactions on Computational Science XIV, LNCS 6970, pages 60-101, 2011.
• Rien van de Weygaert, Pratyush Pranav, Bernard J.T. Jones, E.G. Patrick Bos, Gert Vegter, Herbert Edelsbrunner, Monique Teillaud, Wojciech A. Hellwing, Changbom Park, Johan Hidding, and Mathijs Wintraecken. Probing Dark Energy with Alpha Shapes and Betti Numbers. arxiv.

• Johan Hidding, Rien van de Weijgaert, Gert Vegter, Bernard J.T. Jones, and Monique Teillaud. Video: The Sticky Geometry of the Cosmic Web. Proceedings 28th Annual Symposium on Computational Geometry, pages 421-422, June 2012. 21st Video Review of Computational Geometry.
• Mikhail Bogdanov, Monique Teillaud, and Gert Vegter, Covering spaces and Delaunay triangulations of the 2D flat torus, 28th European Workshop on Computational Geometry, March 2012.