Geometric problems are central in many areas of science and
engineering. Computational geometry, the study of combinatorial and
algorithmic problems in a geometric setting, has tremendous practical
applications in areas such as computer graphics, computer vision and
imaging, scientific visualization, geographic information systems,...
Traditionally, the scope of computational geometry research has been limited to manipulation of geometric elements in the Euclidean space Rd.
|Due to the recent emergence of standardized software libraries, in particular the Computational Geometry Algorithms Library CGAL, developed in the framework of an Open Source Project, the so-far mostly theoretical results developed in computational geometry are being used and extended for practical use like never before.|
Workshop on Computational Geometry, INRIA Sophia Antipolis -
Méditerranée, 8 - 10 Dec 2010
Subdivide and Tile: Triangulating spaces for understanding the world, Lorentz Center, Leiden, The Netherlands, 16 - 20 Nov 2009
CGAL Prospective Workshop on Geometric Computing in Periodic Spaces, INRIA Sophia Antipolis - Méditerranée, 20 October 2008
This work was partially supported by the Triangles contract of the ANR (2007-2010) and of the OrbiCG partnership of the Program "Associate Team" of INRIA (2009-2011).
(image by Manuel Caroli - larger version)
|Manuel Caroli's PhD
discusses triangulations of different topological spaces for
given point sets. We propose both definitions and algorithms
for different classes of spaces and provide an implementation
for the specific case of the three-dimensional flat torus.
The work is originally motivated by the need for software computing three-dimensional periodic Delaunay triangulations in numerous domains including astronomy, material engineering, biomedical computing, fluid dynamics etc. Periodic triangulations can be understood as triangulations of the flat torus. We provide a definition and develop an efficient incremental algorithm to compute Delaunay triangulations of the flat torus [ESA'09]. The algorithm is a modification of the incremental algorithm for computing Delaunay triangulations in Rd. Unlike previous work on periodic triangulations we avoid maintaining several periodic copies of the input point set whenever possible. Also the output of our algorithm is guaranteed to always be a triangulation of the flat torus.
An implementation of our algorithm that has been made available to a broad public as a part of CGAL. This package is already used for instance by researchers in astronomy [astro, orbicg]. See also the [video - The Sticky Geometry of the Cosmic Web ].
We generalize the work on the flat torus onto a more general class of flat orbit spaces [SoCG'11] as well as orbit spaces of constant positive curvature. We furthermore consider the much richer class of orbit spaces of constant negative curvature.
Work is in progress to provide meshings of periodic
surfaces and periodic volumes in CGAL, using the results
obtained on 3D periodic triangulations.
This will have applications in various fields including materials engineering and nano-structures.
(work started during the internship of Vissarion Fisikopoulos)
(work started during the internship of Mikhail Bogdanov)
|In his PhD
thesis, Mikhail Bogdanov
elaborated on the preliminary study done by Manuel
Caroli (see above), on triangulations in hyperbolic manifolds.
We have proopsed a practical algorithm to compute Delaunay
triangulations in the hyperbolic plane, represented as the
Poincaré disk (see picture)
space of circles
gives some mathematical background for this work.
We proved results on cycles in the Delaunay triangulation of closed hyperbolic manifolds [RR 8434].
We considered the problem of computing a triangulation of the real
projective plane P2, given a finite point set S as input.
We prove that a triangulation of P2 always exists if at
least six points in S are in general position, i.e., no three of
them are collinear. We also design an algorithm for triangulating
P2 if this necessary condition holds. As far as we know,
this is the first computational result on the real projective
(work done during the internship of Mridul Aanjaneya)
we propose two approaches for computing the Delaunay
triangulation of points on a sphere, or of rounded points close
to a sphere, both based on the classic incremental algorithm
initially designed for the
We implemented the two approaches in a fully robust way,
building upon existing generic algorithms provided by the CGAL
library. The efficiency and scalability of the method is shown
by benchmarks. We are targetting at a submission to CGAL asap.