More Spaces for Computational Geometry

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 R^d.

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.

To fulfill the promise of applicability of these results for the benefit of both researchers in academia and of the industry, and to expand the scope of some initial efforts, it is important to extend the traditional focus on R^d to encompass other geometric spaces. Impact is expected in various fields like simulation of fluid dynamics, chemical engineering, astronomy, cristallography, computer graphics, computer vision...

• Delaunay Triangulations of closed Euclidean manifolds

  (image by Manuel Caroli - larger version)

  Manuel Caroli's PhD thesis 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.

• Periodic meshes

  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)

• Delaunay Triangulations of hyperbolic manifolds

  In his PhD thesis, Mikhail Bogdanov is elaborating 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) [SoCG'13, RR 8146]. The space of circles gives some mathematical background for this work. A package is under development for CGAL. The current prototype has already been used to compute periodic meshes of the hyperbolic plane [RR 8179] (work started during the internship of Mathieu Schmitt). The work is expected to have applications in various fields, see eg. [GFF'11, CF'09, FCF'10, RFG'10].

• Triangulations of the projective plane

  We considered the problem of computing a triangulation of the real projective plane P², given a finite point set S as input. We prove that a triangulation of P² 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 P² if this necessary condition holds. As far as we know, this is the first computational result on the real projective plane [MACIS'07].
  (work done during the internship of Mridul Aanjaneya)

• Delaynay triangulations of the sphere

  Delaunay triangulation of 20950 weather stations all around the world

  In [SEA'10] 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 plane. 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. (work started during the internship of Olivier Rouiller and improved during the internship of Claudia Werner)