Return to Research

Data Structures and Robust Geometric Computation


We are pursuing efforts to design efficient algorithms both from the theoretical and practical point of view.

We made significant contributions to algorithms for computing Delaunay triangulations. We are still working on the practical efficiency of existing algorithms to compute or to exploit classical Euclidean triangulations in 2 and 3 dimensions, but the current focus of our research is more aimed toward extending the triangulation efforts in several possible directions of generalizations.

One of this direction is the triangulation of non Euclidean spaces such as periodic or projective spaces, with various potential applications ranging from astronomy to granular material simulation.

Another direction is the triangulation of moving points, with potential applications to fluid dynamics where the points represent some particles of some evolving physical material, and to variational methods devised to optimize point placement for meshing a given domain with an high quality elements.

Increasing the dimension of space is also a stimulating direction of research, as triangulating points in medium dimension (say 4 to 15) provides new challenges to trade exponential complexity of the problem in the dimension for the possibility to reach effective and practical result in reasonably small dimension.

On the complexity analysis side, we pursue efforts to get complexity analysis in some practical situation involving randomized or stochastic hypotheses. On the algorithm design side, we are looking for new paradigms to exploit parallelism on modern multicore hardware architectures.