New challenges in triangulations – Triangles

-- Context and motivation. 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 practical applications in areas such as computer graphics, computer vision and imaging, scientific visualization, geographic information systems... We are particularly interested in computing triangulations. Roughly, computing a triangulation consists in, given a set of input points, partitioning the underlying space in simplices whose vertices are the input points. These data structures have tremendous applications, since they are the basis for solving many other problems like meshing and shape reconstruction. Due to the recent emergence of standardized software libraries, in particular the Computational Geometry Algorithms Library CGAL (www.cgal.org), 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 fulfil the promise of applicability of these results for the benefit of researchers in academia and in industry, and to expand the scope of some initial efforts, it is important to extend the traditional focus to take new needs in account : - the temporal dimension, in other words, triangulations of moving points, e.g. for simulation purposes, - the framework of non Euclidean spaces such as periodic spaces - the increasing size of data which implies the use of special compact data structures. -- Objectives. The goal of this research is to develop robust and efficient algorithms for manipulating large sized input, moving points and points in non Euclidean spaces such as periodic spaces (torus, cylinder), oriented projective space, projective space, hyperbolic space. We intend to produce theoretical results and implementation of these algorithms in the widely used CGAL software library. Fundamental problems must be solved, first on the background mathematical definition and properties of geometric structures like triangulations, then on algorithms and data-structures. The originality of this research resides in particular in its multidisciplinarity, ranging from mathematics through algorithmics to computer science and software engineering. We plan to achieve high visibility and practical use of the results by writing and making available through the widely used CGAL a software implementation in terms of extended CGAL kernels for basic primitives in non-Euclidean spaces and for moving points, extended CGAL package for evolving triangulations, triangulations in non Euclidean spaces, and compact data structures. This research will extend CGAL in important and significant ways as well as encourage the use of geometric computing in application areas. We will consider problems of recent and active research interest in various fields to ensure the relevance of our results and applicability, with the aim of making an immediate impact, in collaboration with researchers in computer vision (visual hulls and camera calibration), simulation of fluid dynamics, astronomy, computer graphics (visibility complexes). -- Impact The results are expected to be widely available, both through publications and software implementation to be distributed worldwide and to be used by scientists and engineers in various fields.