Geometric Algorithms & Models Beyond the Linear & Euclidean realm

Department 1 : Algorithms, computation, image and geometry

Team leader : Olivier Devillers
Tél. : 03 83 59 20 70
Mail :



Classical computational geometry usually deals with linear objects in a Euclidean setting and when other situations happen, curved objects are typically linearized and non-Euclidean spaces are locally approximated by Euclidean spaces. The goals of the Gamble team are to address such limitations of classical computational geometry.

Research activities


  • Non-linear computational geometry. Curved objects are ubiquitous in the world we  live in. However, despite this ubiquity and decades of research in several communities, curved  objects are far from being robustly and efficiently manipulated by geometric algorithms. Our  work on, for instance, quadric intersections and certified drawing of plane curves has proven that dramatic improvements can be accomplished when the right mathematics and computer science  are put into motion. In this direction, many problems are fundamental and solutions have  potential industrial impact in Computer Aided Design and Robotics for instance. Intersecting  NURBS and meshing singular surfaces in a certified manner are important examples of such  problems.
  • Non-Euclidean computational geometry. Triangulations are central geometric data  structures in many areas of science and engineering. Traditionally, their study has been limited  to the Euclidean setting. Needs for triangulations in non-Euclidean settings have emerged in  many areas dealing with objects whose sizes range from the nuclear to the astrophysical scale,  and both in academia and in industry. It has become timely to extend the traditional focus on Rd of computational geometry and encompass non-Euclidean spaces.
  • Probability in computational geometry. The design of efficient algorithms is driven  by the analysis of their complexity. Traditionally, worst-case input and sometimes uniform  distributions are considered and many results in these settings have had a great influence on  the domain. Nowadays, it is necessary to be more subtle and to prove new results in between  these two extreme settings. For instance, smoothed analysis, which was introduced for the  simplex algorithm and which we applied successfully to convex hulls, proves that such promising  alternatives exist.



  • QI
  • Isotop
  • CGal


  • Many co-authors on an international scale
  • University of Victoria, University Carleton
  • IRCCyN (Nantes), LIGM (Marne la Vallée)
  • Équipes INRIA DataShape (Saclay) et Ouragan (Paris)


Computational geometry, Computer algebra, Probability, Hyperbolic geometry