RESEARCH CENTRE

Inria Centre
at Université de Lorraine

IN PARTNERSHIP WITH:

Université de Lorraine

2023
ACTIVITY REPORT

Project-Team

GAMBLE

Geometric Algorithms & Models Beyond
the Linear & Euclidean realm

IN COLLABORATION WITH: Laboratoire lorrain de recherche en
informatique et ses applications (LORIA)

DOMAIN

Algorithmics, Programming, Software and
Architecture

THEME

Algorithmics, Computer Algebra and
Cryptology

Contents

Project-Team GAMBLE

1 Team members, visitors, external collaborators

2 Overall objectives

3 Research program

3.1 Non-linear computational geometry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2 Non-Euclidean computational geometry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.3 Probability in computational geometry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.4 Discrete geometric structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4 Application domains

5 Highlights of the year

5.1 Awards . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6 New software, platforms, open data

6.1 New software . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.1.1 pwpoly . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1

2

3

4
4
5
6
6

7

8
8

8
8
8

7 New results

8
8
7.1 Non-Linear Computational Geometry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
7.1.1 Fast evaluation and root finding for polynomials with floating-point coefficients . .
8
. . . . . . . . . . . . .
7.1.2 Fast high-resolution drawing of algebraic curves and surfaces
9
7.2 Non-Euclidean Computational Geometry . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.2.1 Computing a Dirichlet domain for a hyperbolic surface . . . . . . . . . . . . . . . . .
9
7.2.2 A linear bound for the Colin de Verdière parameter for graphs embedded on a surfaces 9
7.2.3 Untangling Graphs on Surfaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
9
7.2.4 Unique ergodicity for infinite area Translation Surfaces . . . . . . . . . . . . . . . . .
7.3 Probabilistic Analysis of Geometric Data Structures and Algorithms . . . . . . . . . . . . . . 10
7.3.1 Two Lower Bounds for Random Point Sets via Negative Association . . . . . . . . . . 10
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
7.4.1 Convex hulls of random order types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
7.4.2 Some new results on geometric transversals . . . . . . . . . . . . . . . . . . . . . . . . 10
. . . . . . . . . . . . . . . . . . . . . 11
7.4.3 A Canonical Tree Decomposition for Chirotopes
7.5 Miscellaneous . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
11
7.5.1 SCARST: Schnyder Compact And Regularity Sensitive Triangulation Data Structure.
7.5.2 Drawing Kn in Three Dimensions with One Bend per Edge . . . . . . . . . . . . . . . 11

7.4 Discrete Geometric structures

8 Bilateral contracts and grants with industry

11
8.1 Bilateral contracts with industry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

8.1.1 WATERLOO MAPLE INC.
8.1.2 GEOMETRYFACTORY

9 Partnerships and cooperations

12
9.1 International initiatives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
9.1.1 Inria associate team not involved in an IIL or an international program . . . . . . . . 12
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
9.1.2 ANR PRCI
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
9.2.1 Visits of international scientists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
9.2.2 Visits to international teams
9.3 National initiatives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
9.3.1 ANR PRC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

9.2 International research visitors

10 Dissemination

14
10.1 Promoting scientific activities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
10.1.1 Scientific events: selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
10.1.2 Journal
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
10.1.3 Software Project . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
10.1.4 Invited talks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
10.1.5 Research administration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
10.1.6 Teaching Committees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
10.2 Teaching - Supervision - Juries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
10.2.1 Teaching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
10.2.2 Supervision . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
10.2.3 Juries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
10.3 Popularization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
10.3.1 Education . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
10.3.2 Interventions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

11 Scientific production

18
11.1 Major publications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
11.2 Publications of the year
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
11.3 Cited publications

Project GAMBLE

1

Project-Team GAMBLE

Creation of the Project-Team: 2017 July 01

Keywords

Computer sciences and digital sciences

A5.5.1. – Geometrical modeling

A5.10.1. – Design

A7.1. – Algorithms

A8.1. – Discrete mathematics, combinatorics

A8.3. – Geometry, Topology

A8.4. – Computer Algebra

Other research topics and application domains

B1.1.1. – Structural biology

B1.2.3. – Computational neurosciences

B2.6. – Biological and medical imaging

B3.3. – Geosciences

B5.5. – Materials

B5.6. – Robotic systems

B5.7. – 3D printing

B6.2.2. – Radio technology

2

Inria Annual Report 2023

1 Team members, visitors, external collaborators

Research Scientists

• Olivier Devillers [Team leader, INRIA, Senior Researcher, HDR]

• Sylvain Lazard [INRIA, Senior Researcher, HDR]

• Guillaume Moroz [INRIA, Researcher]

• Marc Pouget [INRIA, Researcher, HDR]

• Monique Teillaud [INRIA, Senior Researcher, HDR]

Faculty Members

• Vincent Despre [UL, Associate Professor]

• Laurent Dupont [UL, Associate Professor]

• Xavier Goaoc [UL, Professor, HDR]

• Alba Marina Malaga Sabogal [UL, Associate Professor]

Post-Doctoral Fellow

• Florent Koechlin [INRIA, Post-Doctoral Fellow, until Aug 2023]

PhD Students

• Loïc Dubois [Université Gustave Eiffel]

• Nuwan Herath Mudiyanselage [UL, ATER, until Aug 2023]

• Camille Lanuel [UL]

• Leo Valque [UL, ATER, from Sep 2023]

• Leo Valque [UL, until Aug 2023]

• Sarah Wajsbrot [UL, from Oct 2023]

Technical Staff

• Rémi Imbach [INRIA, Engineer, until Oct 2023]

Interns and Apprentices

• Pierre Anxionnat [UL, Intern, until Aug 2023]

• Marguerite Bin [ENS Lyon, Intern, from Oct 2023]

• Taekang Eom [INRIA, Intern, until Feb 2023]

• Sarah Wajsbrot [INRIA, Intern, from Apr 2023 until Sep 2023]

Administrative Assistant

• Cecilia Olivier [INRIA, from Jul 2023]

Project GAMBLE

3

External Collaborator

• Valentin Feray [CNRS, HDR]

2 Overall objectives

Starting in the eighties, the emerging computational geometry community has put a lot of effort into
designing and analyzing algorithms for geometric problems. The most commonly used framework was to
study the worst-case theoretical complexity of geometric problems involving linear objects (points, lines,
polyhedra. . . ) in Euclidean spaces. This so-called classical computational geometry has some known
limitations:

• Objects: dealing with objects only defined by linear equations.

• Ambient space: considering only Euclidean spaces.

• Complexity: worst-case complexities often do not capture realistic behaviour.

• Dimension: complexities are often exponential in the dimension.

• Robustness: ignoring degeneracies and rounding errors.

Even if these limitations have already got some attention from the community [43], a quick look at

the proceedings of the flagship conference SoCG1 shows that these topics still need a big effort.

It should be stressed that, in this document, the notion of certified algorithms is to be understood
with respect to robustness issues. In other words, certification does not refer to programs that are proven
correct with the help of mechanical proof assistants such as Coq, but to algorithms that are proven correct
on paper even in the presence of degeneracies and computer-induced numerical rounding errors.

We address several of the above limitations:

• 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 concepts 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 (Non-uniform rational basis splines) 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.

• Discrete geometric structures. Many geometric algorithms work, explicitly or implicitly, over discrete
structures such as graphs, hypergraphs, lattices that are induced by the geometric input data. For example,
convex hulls or straight-line graph drawing are essentially based on orientation predicates, and therefore
operate on the so-called order type of the input point set. Order types are a subclass of oriented matroids

1Symposium on Computational Geometry. www.computational-geometry.org/.

4

Inria Annual Report 2023

Figure 1: Two views of the Whitney umbrella (on the left, the “stick” of the umbrella, i.e., the negative
z-axis, is missing). Right picture from [Wikipedia], left picture from [Lachaud et al.].

that remains poorly understood: for instance, we do not even know how to sample this space with
reasonable bias. One of our goals is to contribute to the development of these foundations by better
understanding these discrete geometric structures.

3 Research program

3.1 Non-linear computational geometry

As mentioned above, curved objects are ubiquitous in real world problems and in computer science
and, despite this fact, there are very few problems on curved objects that admit robust and efficient
algorithmic solutions without first discretizing the curved objects into meshes. Meshing curved objects
induces a loss of accuracy which is sometimes not an issue but which can also be most problematic
depending on the application. In addition, discretization induces a combinatorial explosion which could
cause a loss in efficiency compared to a direct solution on the curved objects (as our work on quadrics
has demonstrated with flying colors [50, 51, 52, 54, 58]). But it is also crucial to know that even the process
of computing meshes that approximate curved objects is far from being resolved. As a matter of fact there
is no algorithm capable of computing in practice meshes with certified topology of even rather simple
singular (that is auto-intersecting) 3D surfaces, due to the high constants in the theoretical complexity
and the difficulty of handling degenerate cases. Part of the difficulty comes from the unintuitive fact that
the structure of an algebraic object can be quite complicated, as depicted in the Whitney umbrella (see
Figure 1), the surface with equation x2 = y 2z whose origin (the “special” point of the surface) is a vertex
of the arrangement induced by the surface while the singular locus is simply the whole z-axis. Even in 2D,
meshing an algebraic curve with the correct topology, that is in other words producing a correct drawing
of the curve (without knowing where the domain of interest is), is a very difficult problem on which we
have recently made important contributions [36, 37][9].

Thus producing practical, robust, and efficient algorithmic solutions to geometric problems on curved
objects is a challenge on all and even the most basic problems. The basicness and fundamentality of
the two problems we mentioned above on the intersection of 3D quadrics and on the drawing in a
topologically certified way of plane algebraic curves show rather well that the domain is still in its infancy.
And it should be stressed that these two sets of results were not anecdotal but flagship results produced
during the lifetime of the VEGAS team (the team preceding GAMBLE).

There are many problems in this theme that are expected to have high long-term impacts. Intersecting
NURBS (Non-uniform rational basis splines) in a certified way is an important problem in computer-
aided design and manufacturing. As hinted above, meshing objects in a certified way is important when
topology matters. The 2D case, that is essentially drawing plane curves with the correct topology, is a
fundamental problem with far-reaching applications in research or R&D. Notice that on such elementary
problems it is often difficult to predict the reach of the applications; as an example, we were astonished by
the scope of the applications of our software on 3D quadric intersection2 which was used by researchers

2QI: web.

Project GAMBLE

5

Figure 2: Left: 3D mesh of a gyroid (triply periodic surface) [61]. Right: Simulation of a periodic Delaunay
triangulation of the hyperbolic plane [32].

in, for instance, photochemistry, computer vision, statistics and mathematics.

3.2 Non-Euclidean computational geometry

Triangulations, in particular Delaunay triangulations, in the Euclidean space Rd have been extensively
studied throughout the 20th century and they are still a very active research topic. Their mathematical
properties are now well understood, many algorithms to construct them have been proposed and
analyzed (see the book of Aurenhammer et al. [30]). Some members of GAMBLE have been contributing
to these algorithmic advances (see, e.g. [35, 68, 46, 34]); they have also contributed robust and efficient
triangulation packages through the state-of-the-art Computational Geometry Algorithms Library CGAL
whose impact extends far beyond computational geometry. Application fields include particle physics,
fluid dynamics, shape matching, image processing, geometry processing, computer graphics, computer
vision, shape reconstruction, mesh generation, virtual worlds, geophysics, and medical imaging.3

It is fair to say that little has been done on non-Euclidean spaces, in spite of the large number of
questions raised by application domains. Needs for simulations or modeling in a variety of domains4
ranging from the infinitely small (nuclear matter, nano-structures, biological data) to the infinitely
large (astrophysics) have led us to consider 3D periodic Delaunay triangulations, which can be seen as
Delaunay triangulations of the 3D flat torus, i.e., the quotient of R3 under the action of some group of
translations [41]. This work has already yielded a fruitful collaboration with astrophysicists [55, 69] and
new collaborations with physicists are emerging. To the best of our knowledge, our CGAL package [40]
is the only publicly available software that computes Delaunay triangulations of a 3D flat torus, in the
special case where the domain is cubic. This case, although restrictive, is already useful.5 We have also
generalized this algorithm to the case of general d -dimensional compact flat manifolds [42]. As far as
non-compact manifolds are concerned, past approaches, limited to the two-dimensional case, have
stayed theoretical [60].

Interestingly, even for the simple case of triangulations on the sphere, the software packages that are
currently available are far from offering satisfactory solutions in terms of robustness and efficiency [39].
Moreover, while our solution for computing triangulations in hyperbolic spaces can be considered
as ultimate [32], the case of hyperbolic manifolds has hardly been explored. Hyperbolic manifolds are
quotients of a hyperbolic space by some group of hyperbolic isometries. Their triangulations can be seen
as hyperbolic periodic triangulations. Periodic hyperbolic triangulations and meshes appear for instance
in geometric modeling [64], neuromathematics [44], or physics [65]. Even the case of the Bolza surface (a
surface of genus 2, whose fundamental domain is the regular octagon in the hyperbolic plane) shows
mathematical difficulties [33][7].

3See Projects using CGAL for details.
4See CGAL Prospective Workshop on Geometric Computing in Periodic Spaces, Subdivide and Tile: Triangulating
spaces for understanding the world, Computational geometry in non-Euclidean spaces, Shape Up 2015 : Exercises in
Materials Geometry and Topology

5See examples at Projects using CGAL

6

Inria Annual Report 2023

3.3 Probability in computational geometry

In most computational geometry papers, algorithms are analyzed in the worst-case setting. This often
yields too pessimistic complexities that arise only in pathological situations that are unlikely to occur in
practice. On the other hand, probabilistic geometry provides analyses with great precision [62, 63, 38],
but using hypotheses with much more randomness than in most realistic situations. We are developing
new algorithmic designs improving state-of-the-art performance in random settings that are not overly
simplified and that can thus reflect many realistic situations.

Sixteen years ago, smooth analysis was introduced by Spielman and Teng analyzing the simplex
algorithm by averaging on some noise on the data [67] (and they won the Gödel prize). In essence, this
analysis smoothes the complexity around worst-case situations, thus avoiding pathological scenarios
but without considering unrealistic randomness. In that sense, this method makes a bridge between
full randomness and worst case situations by tuning the noise intensity. The analysis of computational
geometry algorithms within this framework is still embryonic. To illustrate the difficulty of the problem,
we started working in 2009 on the smooth analysis of the size of the convex hull of a point set, arguably the
simplest computational geometry data structure; then, only one very rough result from 2004 existed [45]
and we only obtained in 2015 breakthrough results, but still not definitive [48, 47, 53].

Another example of a problem of different flavor concerns Delaunay triangulations, which are rather
ubiquitous in computational geometry. When Delaunay triangulations are computed for reconstructing
meshes from point clouds coming from 3D scanners, the worst-case scenario is, again, too pessimistic
and the full randomness hypothesis is clearly not adapted. Some results exist for “good samplings of
generic surfaces” [29] but the big result that everybody wishes for is an analysis for random samples
(without the extra assumptions hidden in the “good” sampling) of possibly non-generic surfaces.

Trade-offs between full randomness and worst case may also appear in other forms such as dependent
distributions, or random distributions conditioned to be in some special configurations. In particular,
simulating geometric distributions with repulsive properties, such as the determinantal point process, is
currently out of reach for more than a few hundred points [56]. Yet it has practical applications in physics
to simulate particules with repulsion such as electrons [59], to simulate the distribution of network
antennas [31], or in machine learning [57].

3.4 Discrete geometric structures

Our work on discrete geometric structures develops in several directions, each one probing a different
type of structure. Although these objects appear unrelated at first sight, they can be tackled by the same
set of probabilistic and topological tools.

A first research topic is the study of Order types. Order types are combinatorial encodings of finite
(planar) point sets, recording for each triple of points the orientation (clockwise or counterclockwise) of
the triangle they form. This already determines properties such as convex hulls or half-space depths, and
the behaviour of algorithms based on orientation predicates. These properties for all (infinitely many)
n-point sets can be studied through the finitely many order types of size n. Yet, this finite space is poorly
understood: its estimated size leaves an exponential margin of error, no method is known to sample it
without concentrating on a vanishingly small corner, the effect of pattern exclusion or VC dimension-type
restrictions are unknown. These are all directions we actively investigate.

A second research topic is the study of Embedded graphs and simplicial complexes. Many topological
structures can be effectively discretized, for instance combinatorial maps record homotopy classes of
embedded graphs and simplicial complexes represent a large class of topological spaces. This raises
many structural and algorithmic questions on these discrete structures; for example, given a closed walk
in an embedded graph, can we find a cycle of the graph homotopic to that walk? (The complexity status of
that problem is unknown.) Going in the other direction, some purely discrete structures can be given an
associated topological space that reveals some of their properties (e.g. the Nerve theorem for intersection
patterns). An open problem is for instance to obtain fractional Helly theorems for set systems of bounded
topological complexity.

Another research topic is that of Sparse inclusion-exclusion formulas. For any family of sets A1, A2, . . . , An,

Project GAMBLE

by the principle of inclusion-exclusion we have

1(cid:83)n

i =1 Ai

= (cid:88)

I ⊆{1,2,...,n}

(−1)

|I |+11(cid:84)

i ∈I Ai

7

(1)

where 1X is the indicator function of X . This formula is universal (it applies to any family of sets) but
its number of summands grows exponentially with the number n of sets. When the sets are balls, the
formula remains true if the summation is restricted to the regular triangulation; we proved that similar
simplifications are possible whenever the Venn diagram of the Ai is sparse. There is much room for
improvements, both for general set systems and for specific geometric settings. Another interesting
problem is to combine these simplifications with the inclusion-exclusion algorithms developed, for
instance, for graph coloring.

4 Application domains

Many domains of science can benefit from the results developed by GAMBLE. Curves and surfaces are
ubiquitous in all sciences to understand and interpret raw data as well as experimental results. Still, the
non-linear problems we address are rather basic and fundamental, and it is often difficult to predict the
impact of solutions in that area. The short-term industrial impact is likely to be small because, on basic
problems, industries have used ad hoc solutions for decades and have thus got used to it.

The example of our work on quadric intersection is typical: even though we were fully convinced that
intersecting 3D quadrics is such an elementary/fundamental problem that it ought to be useful, we were
the first to be astonished by the scope of the applications of our software 6 (which was the first and still is
the only one —to our knowledge— to compute robustly and efficiently the intersection of 3D quadrics)
which has been used by researchers in, for instance, photochemistry, computer vision, statistics, and
mathematics. Our work on certified drawing of plane (algebraic) curves falls in the same category. It
seems obvious that it is widely useful to be able to draw curves correctly (recall also that part of the
problem is to determine where to look in the plane) but it is quite hard to come up with specific examples
of fields where this is relevant. A contrario, we know that certified meshing is critical in mechanical-
design applications in robotics, which is a non-obvious application field. There, the singularities of
a manipulator often have degrees higher than 10 and meshing the singular locus in a certified way is
currently out of reach. As a result, researchers in robotics can only build physical prototypes for validating,
or not, the approximate solutions given by non-certified numerical algorithms.

The fact that several of our pieces of software for computing non-Euclidean triangulations had already
been requested by users long before they become public in CGAL is a good sign for their wide future
impact. This will not come as a surprise, since most of the questions that we have been studying followed
from discussions with researchers outside computer science and pure mathematics. Such researchers are
either users of our algorithms and software, or we meet them in workshops. Let us only mention a few
names here. Rien van de Weijgaert [55, 69] (astrophysicist, Groningen, NL) and Michael Schindler [66]
(theoretical physicist, ENSPCI, CNRS, France) used our software for 3D periodic weighted triangulations.
Stephen Hyde and Vanessa Robins (applied mathematics and physics at Australian National University)
used our package for 3D periodic meshing. Olivier Faugeras (neuromathematics, INRIA Sophia Antipolis)
had come to us and mentioned his needs for good meshes of the Bolza surface [44] before we started to
study them. Such contacts are very important both to get feedback about our research and to help us
choose problems that are relevant for applications. These problems are at the same time challenging from
the mathematical and algorithmic points of view. Note that our research and our software are generic,
i.e., we are studying fundamental geometric questions, which do not depend on any specific application.
This recipe has made the sucess of the CGAL library.

Probabilistic models for geometric data are widely used to model various situations ranging from
cell phone distribution to quantum mechanics. The impact of our work on probabilistic distributions
is twofold. On the one hand, our studies of properties of geometric objects built on such distributions
will yield a better understanding of the above phenomena and has potential impact in many scientific
domains. On the other hand, our work on simulations of probabilistic distributions will be used by other
teams, more maths oriented, to study these distributions.

6QI: web.

8

Inria Annual Report 2023

5 Highlights of the year

5.1 Awards

The CGAL project, in which we are deeply involved, received a SoCG Test of Time award. Monique Teillaud
and Andreas Fabri (GEOMETRYFACTORY) gave the (video) presentation at the award ceremony.
More information on the Inria website.

6 New software, platforms, open data

6.1 New software

6.1.1 pwpoly

Keywords: Evaluation, Polynomial equations, Complex number

Functional Description: This software uses a new approach to evaluate and find the roots of polynomials
whose coefficients do not all have the same order of magnitude. In particular, after a quasi-linear
pre-processing in degree, the evaluation at a point is done in logarithmic time in degree, with the
same precision as the evaluation of the original polynomial done with floating-point arithmetic.
Moreover, for a well-conditioned polynomial, the calculation of the approximate roots is also
performed in quasi-linear time in degree.

Publication: https://inria.hal.science/hal-03980098

Authors: Remi Imbach, Guillaume Moroz

Contact: Guillaume Moroz

7 New results

7.1 Non-Linear Computational Geometry

Participants:

Laurent Dupont, Nuwan Herath Mudiyanselage, Sylvain Lazard, Guil-
laume Moroz, Marc Pouget.

7.1.1 Fast evaluation and root finding for polynomials with floating-point coefficients

Evaluating or finding the roots of a polynomial f (z) = f0 + · · · + fd zd with floating-point number coef-
ficients is a ubiquitous problem. By using a piecewise approximation of f obtained with a careful use
of the Newton polygon of f , we improved state-of-the-art upper bounds on the number of operations
to evaluate and find the roots of a polynomial. In particular, if the coefficients of f are given with m
significant bits, we provided for the first time an algorithm that finds all the roots of f with a relative
condition number lower than 2m, using a number of bit operations quasi-linear in the bit-size of the
floating-point representation of f . Notably, our new approach handles efficiently polynomials with
−d to 2d , both in theory and in practice. This work was published at the ISSAC
coefficients ranging from 2
2024 conference [16] and led to the developpement of the software pwpoly that is in the process of being
included in Maple 2024.

7.1.2 Fast high-resolution drawing of algebraic curves and surfaces

We addressed the problem of computing a drawing of high resolution of a plane curve defined by a
bivariate polynomial equation P (x, y) = 0. Given a grid of fixed resolution, a drawing is a subset of pixels.
Our goal is to compute an approximate drawing that (i) contains all the parts of the curve that intersect
the pixel edges, (ii) excludes a pixel when the evaluation of P with interval arithmetic on each of its

Project GAMBLE

9

four edges does not contain zero. Most state-of-the-art approaches focus on bounding the number of
independent evaluations. One of the challenges for computing drawings of high degree curves on a
high-resolution grid is to minimize the complexity due to the many evaluations of the input polynomial.
Using state-of-the-art Computer Algebra techniques, we designed new algorithms that amortize the
evaluations and improve the complexity for computing such drawings. Our main contribution was to use
a non-uniform grid based on the Chebyshev nodes to take advantage of multipoint evaluation techniques
via the Discrete Cosine Transform. This work was the topic of Nuwan Herath’s PhD thesis [19].

7.2 Non-Euclidean Computational Geometry

Participants:

Vincent Despré, Loïc Dubois, Camille Lanuel, Alba Marina Málaga
Sabogal, Monique Teillaud.

7.2.1 Computing a Dirichlet domain for a hyperbolic surface

This paper exhibits and analyzes an algorithm that takes a given closed orientable hyperbolic surface
and outputs an explicit Dirichlet domain. The input is a fundamental polygon with side pairings. While
grounded in topological considerations, the algorithm makes key use of the geometry of the surface. We
introduce data structures that reflect this interplay between geometry and topology and show that the
algorithm runs in polynomial time, in terms of the initial perimeter and the genus of the surface [15].

In collaboration with Benedikt Kolbe (now at University of Bonn) and Hugo Parlier (University of

Luxembourg).

7.2.2 A linear bound for the Colin de Verdière parameter for graphs embedded on a surfaces

The Colin de Verdière graph parameter µ(G) was introduced in 1990 by Y. Colin de Verdière. It is defined
via spectral properties of a certain type of matrices, called Schrödinger operators, associated to a graph G.
We provide a combinatorial and self-contained proof that for all graphs G embedded on a surface S, the
Colin de Verdière parameter µ(G) is upper bounded by 7 − 2χ(S), where χ(S) is the Euler characteristic of
S [17, 24].

In collaboration with Francis Lazarus (CNRS, G-SCOP) and Rudi Pendavingh ( TU/e - Eindhoven

University of Technology).

7.2.3 Untangling Graphs on Surfaces

Consider a graph drawn on a surface (for example, the plane minus a finite set of obstacle points), possibly
with crossings. We provide an algorithm to decide whether such a drawing can be untangled, namely, if
one can slide the vertices and edges of the graph on the surface (avoiding the obstacles) to remove all
crossings; in other words, whether the drawing is homotopic to an embedding. While the problem boils
down to planarity testing when the surface is the sphere or the disk (or equivalently the plane without any
obstacle), the other cases have never been studied before, except when the input graph is a cycle, in an
abundant literature in topology and more recently by Despré and Lazarus [SoCG 2017, J. ACM 2019], who
gave a near-linear algorithm for this problem. Our algorithm runs in O(m + (g + b)n log n) time, where
g ≥ 0 and b ≥ 0 are the genus and the number of boundary components of the input orientable surface Σ,
and n is the size of the input graph drawing, lying on some fixed graph of size m cellularly embedded
on Σ [22].

In collaboration with Éric Colin de Verdière (CNRS, Laboratoire d’Informatique Gaspard-Monge).

7.2.4 Unique ergodicity for infinite area Translation Surfaces

We consider infinite staircase translation surfaces with varying step sizes. We show that for typical step
sizes, up to scaling, the translation flow has a unique invariant, non-atomic, ergodic Radon measure in
almost every direction [25].

In collaboration with Serge Troubetzkoy (Institut de Mathématiques de Marseille).

10

Inria Annual Report 2023

7.3 Probabilistic Analysis of Geometric Data Structures and Algorithms

Participants: Olivier Devillers, Xavier Goaoc.

7.3.1 Two Lower Bounds for Random Point Sets via Negative Association

We present two lower bounds that hold with high probability for random point sets. We first give a new,
and elementary, proof that the classical models of random point sets (uniform in a smooth convex body,
uniform in a polygon, Gaussian) have a superconstant number of extreme points with high probability.
We next prove that any algorithm that determines the orientation of all triples in a planar set of n points
(that is, the order type of the point set) from their Cartesian coordinates must read with high probability
4n log n − O(n log log n) coordinate bits. This matches previously known upper bounds. Both bounds
rely on a method due to Dubhashi and Ranjan [49] for obtaining concentration results via a negative
association property [20].

In collaboration with Denys Bulavka (Charles University, Prague) , Philippe Duchon (LaBRI, Bordeaux),

and Marc Glisse (Inria-DATASHAPE).

7.4 Discrete Geometric structures

Participants:

Florent Koechlin, Xavier Goaoc, Sarah Wajsbrot.

7.4.1 Convex hulls of random order types

We establish the following two main results on order types of points in general position in the plane
(realizable simple planar order types, realizable uniform acyclic oriented matroids of rank 3):

(a) The number of extreme points in an n-point order type, chosen uniformly at random from all
and

such order types, is on average 4 + o(1). For labeled order types, this number has average 4 −
variance at most 3.

8
n2−n+2

(b) The (labeled) order types read off a set of n points sampled independently from the uniform meas-
ure on a convex planar domain, smooth or polygonal, or from a Gaussian distribution are concentrated,
i.e., such sampling typically encounters only a vanishingly small fraction of all order types of the given
size.

Result (a) generalizes to arbitrary dimension d for labeled order types with the average number of
extreme points 2d + o(1) and constant variance. We also discuss to what extent our methods generalize
to the abstract setting of uniform acyclic oriented matroids. Moreover, our methods show the following
relative of the Erd˝os-Szekeres theorem: for any fixed k, as n → ∞, a proportion 1 − O(1/n) of the n-point
simple order types contain a triangle enclosing a convex k-chain over an edge.

For the unlabeled case in (a), we prove that for any antipodal, finite subset of the two-dimensional
sphere, the group of orientation preserving bijections is cyclic, dihedral, or one of A4, S4, or A5 (and
each case is possible). These are the finite subgroups of SO(3) and our proof follows the lines of their
characterization by Felix Klein. This work appeared in the Journal of the ACM [13].

In collaboration with Emo Welzl (ETH Zürich).

7.4.2 Some new results on geometric transversals

We investigate a number of questions, problems, and conjectures related to geometric transversal theory.
Among our results we disprove a conjecture of Bárány and Kalai regarding weak ϵ-nets for k-flats and
convex sets in Rd and we prove a conjecture of Arocha, Bracho, and Montejano regarding a colorful version
of the Goodman–Pollack–Wenger transversal theorem. We also investigate the connected components of
the space of line transversals to pairwise disjoint convex sets in R3 and we extend a theorem of Karasev and

Project GAMBLE

11

Montejano regarding colorful intersections and k-transversals. This work was accepted for publication in
Discrete & Computational Geometry [12].

In collaboration with Otfried Cheong (SCALGO) and Andreas Holmsen (KAIST).

7.4.3 A Canonical Tree Decomposition for Chirotopes

We introduce and study a notion of decomposition of planar point sets (or rather of their chirotopes) as
trees decorated by smaller chirotopes. This decomposition is based on the concept of mutually avoiding
sets, and adapts in some sense the modular decomposition of graphs in the world of chirotopes. The
associated tree always exists and is unique up to some appropriate constraints. We also show how to
compute the number of triangulations of a chirotope efficiently, starting from its tree and the (weighted)
numbers of triangulations of its parts.

In collaboration with Mathilde Bouvel (INRIA project Team MOCQUA) and Valentin Feray (IECL,

Nancy).

7.5 Miscellaneous

Participant: Olivier Devillers, Sylvain Lazard.

7.5.1 SCARST: Schnyder Compact And Regularity Sensitive Triangulation Data Structure.

We consider the problem of designing fast and compact solutions for representing the connectivity
information of triangle meshes. While traditional data structures (Half-Edge, Corner Table) are fast
and user-friendly, they tend to be memory-expensive. On the other hand, compression schemes, while
meeting information-theory lower bounds, lack the ability to facilitate rapid navigation within the
mesh structure. Compact representations provide an advantageous balance for representing large
meshes, enabling a judicious compromise between memory consumption and fast implementation of
navigational operations. We propose new representations that are sensitive to the regularity of the graph
while still having worst case guarantees. For all our data structures we have both an interesting storage
cost, typically 2 or 3 r.p.v. (references/vertex) in the case of very regular triangulations and provable
upper bounds in the worst case scenario. One of our solution has a worst case cost of 3.33 r.p.v. which
is currently the best-known bound improving the previous 4 r.p.v. [28]. In terms of running time, our
representations are slightly slower (factor 1.5 to 4) than classical data structures. In our experiments we
compare on various meshes runtime and memory performance of our representations with those of the
most efficient existing solutions [21].

In collaboration with Luca Castelli Aleardi (LIX)

7.5.2 Drawing Kn in Three Dimensions with One Bend per Edge

We present a drawing of Kn in three dimensions in which vertices are placed at integer grid points and
edges are drawn crossing-free with at most one bend per edge; the bend points are also placed at integer
grid points. The drawing is determined by an incremental algorithm and the observed behavior of the
algorithm produces an output of volume close to quadratic [23, 26].

8 Bilateral contracts and grants with industry

8.1 Bilateral contracts with industry

8.1.1 WATERLOO MAPLE INC.

Participants:

Laurent Dupont, Sylvain Lazard, Guillaume Moroz, Marc Pouget,
Rémi Imbach.

12

Inria Annual Report 2023

Company: WATERLOO MAPLE INC.
Duration: 2 years, renewable
Participants: GAMBLE and OURAGAN Inria teams

Abstract: A renewable two-years licence and cooperation agreement was signed on April 1st, 2018
between WATERLOO MAPLE INC., Ontario, Canada (represented by Laurent Bernardin, its Executive Vice
President Products and Solutions) and Inria. On the Inria side, this contract involves the teams GAMBLE
and OURAGAN (Paris), and it is coordinated by Fabrice Rouillier (OURAGAN).

F. Rouillier and GAMBLE are the developers of the ISOTOP software for the computation of topology of

curves. The transfer of a version of ISOTOP to WATERLOO MAPLE INC. should be done on the long run.

This contract was amended last year to include the new software HEFROOTS for the isolation of the
complex roots of a univariate polynomial. The transfer of HEFROOTS to WATERLOO MAPLE INC. started at
the end of 2021 with the help of the independent contractor Rémi Imbach. Rémi Imbach was then hired
for one year by Inria through the ADT program. This led to the inclusion of HEFROOTS in Maple 2023, and
to the development of a improved software PWPOLY that is planned to be included in Maple 2024.

8.1.2 GEOMETRYFACTORY

Participants: Monique Teillaud.

Company: GEOMETRYFACTORY
Duration: permanent
Participants: INRIA and GEOMETRYFACTORY
Abstract: CGAL packages developed in GAMBLE are commercialized by GEOMETRYFACTORY.

9 Partnerships and cooperations

9.1 International initiatives

9.1.1 Inria associate team not involved in an IIL or an international program

FIP

Title: Finite point sets and Intersection Patterns

Duration: January 2021 to December 2023

Coordinators: Xavier Goaoc and Andreas Holmsen (andreash@kaist.edu)

Partners:

• Korea Advanced Institute of Science and Technology Daejeon (Corée du Sud)

Inria contact: Xavier Goaoc

Summary: This project tackles two families of problems in discrete and computational geometry, dealing
respectively with finite point sets and to intersection patterns of geometric set systems. The two PI
already collaborate on one family of problems and have worked independently on the other. The
goal of the associate team is to broaden this two-person collaboration, and help the emergence of
new research groups.

9.1.2 ANR PRCI

ANR SoS

Title: Structures on Surfaces

Project GAMBLE

13

Duration: 4 years + 1 year Covid’19 extension

Starting date: April 1st, 2018

Coordinator: Monique Teillaud

Partners:

• Gamble project-team, Inria.

• LIGM (Laboratoire d’Informatique Gaspard Monge), Université Gustave Eiffel. Local Coordin-

ator: Éric Colin de Verdière.

• RMATH (Mathematics Research Unit), University of Luxembourg. National Coordinator:

Hugo Parlier.

Inria contact: Monique Teillaud

Summary: SoS is co-funded by ANR (ANR-17-CE40-0033) and FNR (INTER/ANR/16/11554412/SoS) as a

PRCI (Projet de Recherche Collaborative Internationale).

The central theme of this project is the study of geometric and combinatorial structures related to
surfaces and their moduli. Even though they work on common themes, there is a real gap between
communities working in geometric topology and computational geometry and SoS aims to create
a long-lasting bridge between them. Beyond a common interest, techniques from both ends are
relevant and the potential gain in perspective from long-term collaborations is truly thrilling.

In particular, SoS aims to extend the scope of computational geometry, a field at the interface
between mathematics and computer science that develops algorithms for geometric problems, to
a variety of unexplored contexts. During the last two decades, research in computational geometry
has gained wide impact through CGAL, the Computational Geometry Algorithms Library. In parallel,
the needs for non-Euclidean geometries are arising, e.g., in geometric modeling, neuromathematics,
or physics. Our goal is to develop computational geometry for some of these non-Euclidean spaces
and make these developments readily available for users in academia and industry.

To reach this aim, SoS follows an interdisciplinary approach, gathering researchers whose expertise
cover a large range of mathematics, algorithms and software. A mathematical study of the objects
considered is performed, together with the design of algorithms when applicable. Algorithms are
analyzed both in theory and in practice after prototype implementations, which are improved
whenever it makes sense to target longer-term integration into CGAL.

Our main objects of study are Delaunay triangulations and circle patterns on surfaces, polyhedral
geometry, and systems of disjoint curves and graphs on surfaces.

Workshop An SoS retreat was organized at Schloss Dagstuhl (Jan 30 - Feb 03).

Project website: sos.loria.fr

9.2 International research visitors

9.2.1 Visits of international scientists

• Andreas Holmsen, Professor, KAIST (June 23rd – July 18th),

• Boris Bukh, Professor, Carnegie Mellon University (July 1–8),

• Denys Bulavka, PhD student, Charles University, Prague (August 21–25),

• Jean Cardinal, Professor, Université Libre de Bruxelles (October 26–27).

9.2.2 Visits to international teams

Research stays abroad Vincent Despre, Loîc Dubois, and Monique Teillaud visited EPFL for one week
and worked with Peter Buser, together with Hugo Parlier (University of Luxembourg).

14

Inria Annual Report 2023

9.3 National initiatives

9.3.1 ANR PRC

ANR MIN-MAX

Title: MIN-MAX

Duration: 2019 to 2023

Coordinator: Stéphane Sabourau (Université Paris-Est Créteil)

Partners:

• Université Paris Est Créteil, Laboratoire d’Analyse et de Mathématiques Appliquées (LAMA).

Local coordinator: Stéphane Sabourau

• Université de Tours, Institut Denis Poisson. Local coordinator: Laurent Mazet. This node
includes two participants from Nancy, Benoît Daniel (IECL) and Xavier Goaoc (Loria, Gamble).

Inria contact: Xavier Goaoc

Summary: The MinMax projet is funded by ANR under number ANR-19-CE40-0014

This collaborative research project aims to bring together researchers from various areas – namely,
geometry and topology, minimal surface theory and geometric analysis, and computational geo-
metry and algorithms – to work on a precise theme around min-max constructions and waist
estimates.

Projetc website: perso.math.u-pem.fr/sabourau.stephane/min-max/

10 Dissemination

10.1 Promoting scientific activities

10.1.1 Scientific events: selection

Reviewer All members of the team are regular reviewers for the conferences of our field, namely Sym-
posium on Computational Geometry (SoCG), European Symposium on Algorithms (ESA), Symposium on
Discrete Algorithms (SODA), International Symposium on Symbolic and Algebraic Computation (ISSAC),
etc.

10.1.2 Journal

Member of the editorial boards Monique Teillaud is a managing editor of JoCG, Journal of Computa-
tional Geometry.

Reviewer - reviewing activities All members of the team are regular reviewers for the journals of
our field, namely Discrete and Computational Geometry (DCG), Journal of Computational Geometry
(JoCG), International Journal on Computational Geometry and Applications (IJCGA), Journal on Symbolic
Computations (JSC), SIAM Journal on Computing (SICOMP), Mathematics in Computer Science (MCS),
etc.

10.1.3 Software Project

Member of the Editorial Boards Marc Pouget and Monique Teillaud are members of the CGAL editorial
board.

Project GAMBLE

10.1.4 Invited talks

15

Monique Teillaud gave a keynote talk “The CGAL project” at the 31st International Symposium on Graph
Drawing and Network Visualization (September, Palermo) [14].

Guillaume Moroz gave an invited talk "Efficient approximation of polynomials" at Rencontres Arith-

métiques du GdR Informatique Mathématique (October, Nancy).

Guillaume Moroz gave an invited talk at the workshop Fundamental Algorithms and Algorithmic

Complexity (September).

Monique Teillaud was invited to be a speaker at the workshop Renormalization, computation and
visualization in Geometry, Number Theory and Dynamics (September, CIRM): “Triangulations, CGAL,
and hyperbolic surfaces” [18].

10.1.5 Research administration

Team members are involved in various committees managing the scientific life of the lab or at a national
level.

Local

• INRIA Comission Information et Édition Scientifique (Laurent Dupont),

• Fédération Charles Hermite (Xavier Goaoc),

• INRIA Comité de centre (Xavier Goaoc),

• LORIA Conseil scientifique (Sylvain Lazard),

• LORIA department chair (Sylvain Lazard),

• LORIA associate director (Sylvain Lazard),

• Computer science board in the École doctorale IAEM (Sylvain Lazard),

• INRIA Comité des utilisateurs des moyens informatiques (chair, Guillaume Moroz)

• INRIA Commission de développement technologique (Guillaume Moroz),

• CLHSCT (Guillaume Moroz),

• INRIA PhD and postdoc hiring committee (Marc Pouget),

• LORIA Conseil de laboratoire (Monique Teillaud),

• Co-organization of “Tutotechno” (Monique Teillaud),

• Setting up a mentoring action at LORIA (Monique Teillaud).

National

• INRIA Mission Jeunes Chercheurs (chair, Sylvain Lazard).

Hiring Committees

• Olivier Devillers chaired the hiring committee for a Professor position at Polytech (Université de

Lorraine).

• Monique Teillaud was a member of the hiring committee for a Professor position at Université

Gustave Eiffel in Marne-la-Vallée.

• Guillaume Moroz was a member of the hiring committee for CRCN/ISFP positions at INRIA Nancy

Grand Est in 2023.

16

Inria Annual Report 2023

Evaluation Committees

• HCERES committee for DIENS ENS Paris (Sylvain Lazard).

10.1.6 Teaching Committees

• Vincent Despre: Head of the Engineer diploma speciality SIR, Systèmes d’Information et Réseaux,

Polytech Nancy, Université de Lorraine.

• Laurent Dupont is the secretary of Commission Pédagogique Nationale Carrières Sociales / Information-

Communication / Métiers du Multimédia et de l’Internet (2017-2022).

• Laurent Dupont represents the Commission Pédagogique Nationale Carrières Sociales / Information-

Communication / Métiers du Multimédia et de l’Internet at the national working group on D.U.T/B.U.T
reform.

• Laurent Dupont: Head of the Bachelor diploma Licence Professionnelle Animateur, Facilitateur de

Tiers-lieux Eco-Responsables, Université de Lorraine.

• Laurent Dupont: Responsible of fablab "Charlylab" of I.U.T. Nancy-Charlemagne,

• Xavier Goaoc is the chair of the computer science department of l’École des Mines de Nancy.

• Xavier Goaoc is a member of the Conseil d’administration de l’École des Mines de Nancy.

10.2 Teaching - Supervision - Juries

10.2.1 Teaching

• Licence: Vincent Despre, Algorithmique, 44h, L2 PEIP, Polytech Nancy, France.

• Licence: Vincent Despre, Programmation orientée objet, 84h, L3 IA2R, Polytech Nancy, France.

• Master: Xavier Goaoc, Modèles d’environnements, planification de trajectoires, 12h, M2 AVR,

Université de Lorraine, France (web).

• Licence: Laurent Dupont, Web development, 45h, L1, Université de Lorraine, France.

• Licence: Laurent Dupont, Web development, 150h, L2, Université de Lorraine, France.

• Licence: Laurent Dupont, Web development and Social networks 70h L3, Université de Lorraine,

France.

• Licence: Laurent Dupont, 3D printing and CAO 40h, L3, Université de Lorraine, France.

• Licence : Xavier Goaoc, Algorithms and complexity, 57 HETD, L3, École des Mines de Nancy, France.

• Master: Xavier Goaoc, Computer architecture, 32 HETD, M1, École des Mines de Nancy Nancy,

France.

• Master: Xavier Goaoc, Introduction to blockchains, 32 HETD, M1, École des Mines de Nancy, France.

• Licence: Alba Marina Malaga Sabogal, Information systems and databases, 86h, L1, Université de

Lorraine, France.

• Licence: Alba Marina Malaga Sabogal, Content Management Systems, 40h, L1, Université de Lor-

raine, France.

• Master: Marc Pouget, Introduction to computational geometry, 10.5h, M2, École Nationale Supérieure

de Géologie, France.

Project GAMBLE

10.2.2 Supervision

17

• PhD defended in June 2023: Nuwan Herath Mudiyanselage, Fast algorithm for the visualization of

surfaces, supervised by Guillaume Moroz and Marc Pouget.

• PhD in progress: Loïc Dubois, Untangling graphs on surfaces, started in Oct. 2022, supervised by

Vincent Despre and Éric Colin de Verdière (Marne la Vallée).

• PhD in progress: Camille Lanuel, A toolbox for hyperbolic surfaces, started in Oct. 2022, supervised

by Vincent Despre and Monique Teillaud.

• PhD in progress: Leo Valque, Rounding 3D meshes, started in Sept. 2020, supervised by Sylvain Laz-

ard.

• PhD in progress: Sarah Wajsbrot, Combinatorial convexity, its generalizations and applications to

optimization, started in Oct. 2023, supervised by Xavier Goaoc.

• Master internship M2: Marguerite Bin, Homological VC dimension following Kalai and Meshulam,

started in Oct. 2023, supervised by Xavier Goaoc.

10.2.3 Juries

• Xavier Goaoc chaired the PhD defense committee of Daria Pchelina, Université Sorbonne Paris

Nord.

• Xavier Goaoc was on the reading and defense committees of the PhD thesis of Theophile Buffière,

Université Sorbonne Paris Nord.

• Xavier Goaoc chaired the PhD defense committee of Guillaume Coiffier, Université de Lorraine.

• Sylvain Lazard chaired the PhD defense committee of Jiayi Wei, École Polytechnique.

• Sylvain Lazard chaired the PhD defense committee of Melike Aydinlilar, Université de Lorraine.

• Marc Pouget was on the PhD defense committee of Christina Katsamaki, Sorbonne Université.

• Monique Teillaud chaired the PhD defense committee of Djamel Eddine Amir, Université de

Lorraine.

10.3 Popularization

• Alba Málaga is a member of the scientific board for the association Les maths en scène and the

marraine for a high-school math student club in Thionville, le labo Rosa Parks.

10.3.1 Education

• Olivier Devillers presented research carreer in several different classes in highschool within the

Chiche program.

• Alba Málaga , for the Festival "Printemps des mathématiques" (23-25 mars 2025), coordinated
and participated in a booth promoting sharing platforms for mathematical communication like
Imaginary, or kits math.

18

Inria Annual Report 2023

10.3.2 Interventions

• Alba Málaga gave two general audience talks for motivated high school students

– «Diplotores, une famille de tores plats polyèdraux» at the MATh.en.JEANS, annual east meet-

ing, Mulhouse, 26/05/2023,

– a talk at the holiday workshop « Les maths, de l’Espace aux espaces » of the association Science

Ouverte, Paris, 28/02/2023.

• Alba Marina Malaga Sabogal and Laurent Dupont organized "Fabrikathon" in April 25, 26, 27, 28 at

IUT Nancy-Charlemagne.

11 Scientific production

11.1 Major publications

[1] N. Chenavier and O. Devillers. ‘Stretch Factor in a Planar Poisson-Delaunay Triangulation with a
Large Intensity’. In: Advances in Applied Probability 50.1 (2018), pp. 35–56. DOI: 10.1017/apr.201
8.3. URL: https://hal.inria.fr/hal-01700778.

[2] V. Despré, J.-M. Schlenker and M. Teillaud. ‘Flipping Geometric Triangulations on Hyperbolic
Surfaces’. In: SoCG 2020 - 36th International Symposium on Computational Geometry. Zurich,
Switzerland, 2020. DOI: 10.4230/LIPIcs.SoCG.2020.35. URL: https://hal.inria.fr/hal-0
2886493.

[3] O. Devillers, S. Lazard and W. Lenhart. ‘Rounding meshes in 3D’. In: Discrete and Computational
Geometry (Apr. 2020). DOI: 10.1007/s00454-020-00202-2. URL: https://hal.inria.fr/hal-
02549290.

[4] X. Goaoc, P. Paták, Z. Patáková, M. Tancer and U. Wagner. ‘Shellability is NP-complete’. In: Journal
of the ACM (JACM) 66.3 (2019). DOI: 10.1145/3314024. URL: https://hal.inria.fr/hal-020
50505.

[5] X. Goaoc and E. Welzl. ‘Convex Hulls of Random Order Types’. In: SoCG 2020 - 36th International
Symposium on Computational Geometry. Ed. by S. Cabello and D. Z. Chen. Vol. 164. 36th Interna-
tional Symposium on Computational Geometry (SoCG 2020). Best paper award. Zürich / Virtual,
Switzerland, 2020, 49:1–49:15. DOI: 10.4230/LIPIcs.SoCG.2020.49. URL: https://hal.inria
.fr/hal-02879289.

[6] R. Imbach, M. Pouget and C. Yap. ‘Clustering Complex Zeros of Triangular Systems of Polynomials’.
In: Mathematics in Computer Science (June 2020). DOI: 10.1007/s11786- 020- 00482- 0. URL:
https://inria.hal.science/hal-02878388.

[7]

I. Iordanov and M. Teillaud. ‘Implementing Delaunay Triangulations of the Bolza Surface’. In: 33rd
International Symposium on Computational Geometry (SoCG 2017). Brisbane, Australia, July 2017,
44:1–44:15. DOI: 10.4230/LIPIcs.SoCG.2017.44. URL: https://hal.inria.fr/hal-015680
02.

[8] R. Jha, D. Chablat, L. Baron, F. Rouillier and G. Moroz. ‘Workspace, Joint space and Singularities of a
family of Delta-Like Robot’. In: Mechanism and Machine Theory 127 (Sept. 2018), pp. 73–95. DOI:
10.1016/j.mechmachtheory.2018.05.004. URL: https://hal.archives-ouvertes.fr/ha
l-01796066.

[9] S. Lazard, M. Pouget and F. Rouillier. ‘Bivariate triangular decompositions in the presence of
asymptotes’. In: Journal of Symbolic Computation 82 (2017), pp. 123–133. DOI: 10.1016/j.jsc.20
17.01.004. URL: https://hal.inria.fr/hal-01468796.

[10] G. Moroz. ‘New data structure for univariate polynomial approximation and applications to root
isolation, numerical multipoint evaluation, and other problems’. In: 2021 IEEE 62nd Annual Sym-
posimum on Foundations of Computer Science (FOCS). FOCS 2021 - 62nd Annual IEEE Sym-
posimum on Foundations of Computer Science. Denver, United States, Dec. 2021. DOI: 10.1109
/FOCS52979.2021.00108. URL: https://hal.science/hal-03249123.

Project GAMBLE

19

11.2 Publications of the year

International journals

[11] O. Cheong, O. Devillers, J.-W. Park and M. Glisse. ‘Covering families of triangles’. In: Periodica
Mathematica Hungarica 87 (2023), pp. 86–109. DOI: 10 . 1007 / s10998 - 022 - 00503 - 4. URL:
https://inria.hal.science/hal-03662311.

[12] O. Cheong, X. Goaoc and A. Holmsen. ‘Some New Results on Geometric Transversals’. In: Discrete
and Computational Geometry (16th Nov. 2023). DOI: 10 . 1007 / s00454 - 023 - 00573 - 2. URL:
https://hal.science/hal-04293155.

[13] X. Goaoc and E. Welzl. ‘Convex Hulls of Random Order Types’. In: Journal of the ACM (JACM) 70.1
(16th Jan. 2023), pp. 1–47. DOI: 10.1145/3570636. URL: https://inria.hal.science/hal-03
831575.

Invited conferences

[14] M. Teillaud. ‘The CGAL Project’. In: 31st International Symposium on Graph Drawing and Network

Visualization. Palerme, Italy, Sept. 2023. URL: https://inria.hal.science/hal-04241529.

International peer-reviewed conferences

[15] V. Despré, B. Kolbe, H. Parlier and M. Teillaud. ‘Computing a Dirichlet Domain for a Hyperbolic Sur-
face’. In: Leibniz International Proceedings in Informatics (LIPIcs). 39th International Symposium
on Computational Geometry (SoCG 2023). Dallas, United States, 9th June 2023, 27:1–27:15. DOI:
10.4230/LIPIcs.SoCG.2023.27. URL: https://inria.hal.science/hal-04125470.

[16] R. Imbach and G. Moroz. ‘Fast evaluation and root finding for polynomials with floating-point
coefficients’. In: ISSAC ’23: Proceedings of the 2023 International Symposium on Symbolic and
Algebraic Computation. ISSAC 2023. Tromsø, Norway, 24th July 2023. URL: https://inria.hal.s
cience/hal-03980098.

Conferences without proceedings

[17] C. Lanuel, F. Lazarus and R. Pendavingh. ‘A linear bound for the Colin de Verdière parameter µ
for graphs embedded on surfaces’. In: EuroCG’23 (39th European Workshop on Computational
Geometry). Barcelona, Spain, Mar. 2023. URL: https://hal.science/hal-04018060.

[18] M. Teillaud. ‘Triangulations, CGAL, and hyperbolic surfaces’. In: Renormalization, computation and
visualization in Geometry, Number Theory and Dynamics. Marseille (CIRM, Centre International
de Rencontres Mathématiques), France, Sept. 2023. URL: https://inria.hal.science/hal-04
241550.

Doctoral dissertations and habilitation theses

[19] N. H. Mudiyanselage. ‘Fast high-resolution drawing of algebraic curves and surfaces’. Université de

Lorraine, 2nd June 2023. URL: https://theses.hal.science/tel-04176128.

Reports & preprints

[20] D. Bulavka, O. Devillers, P. Duchon, M. Glisse and X. Goaoc. Two Lower Bounds for Random Point
Sets via Negative Association. 2023. URL: https://inria.hal.science/hal-04320184.

[21] L. Castelli Aleardi and O. Devillers. SCARST: Schnyder Compact And Regularity Sensitive Triangula-

tion Data Structure. 2023. URL: https://inria.hal.science/hal-04320292.

[22] É. Colin de Verdière, V. Despré and L. Dubois. Untangling Graphs on Surfaces. 2023. DOI: 10.48550

/arXiv.2311.00437. URL: https://inria.hal.science/hal-04323774.

[23] O. Devillers and S. Lazard. Drawing Kn in Three Dimensions with One Bend per Edge, revisited. 2023.

URL: https://inria.hal.science/hal-04182069.

20

Inria Annual Report 2023

[24] C. Lanuel, F. Lazarus and R. Pendavingh. A linear bound for the Colin de Verdière parameter µ for
graphs embedded on surfaces. 1st Mar. 2023. URL: https://hal.science/hal-04010163.

[25] A. M. Málaga Sabogal and S. Troubetzkoy. Unique ergodicity for infinite area Translation Surfaces.

21st July 2023. URL: https://hal.science/hal-02265283.

Other scientific publications

[26] O. Devillers and S. Lazard. ‘One-Bend Drawing of Kn in 3D, revisited’. In: The 31st International
Symposium on Graph Drawing and Network Visualization. Palermo, Italy: Springer, 2023. URL:
https://inria.hal.science/hal-04195317.

[27] X. Goaoc and M. Kerber. Guest Editors’ Foreword special issue of Discrete & Computational Geometry.
16th Nov. 2023. DOI: 10.1007/s00454-023-00618-6. URL: https://inria.hal.science/hal-
04312308.

11.3 Cited publications

[28] L. C. Aleardi and O. Devillers. ‘Array-based compact data structures for triangulations: Practical
solutions with theoretical guarantees’. In: J. Comput. Geom. 9.1 (2018), pp. 247–289. DOI: 10.20382
/jocg.v9i1a8.

[29] D. Attali, J.-D. Boissonnat and A. Lieutier. ‘Complexity of the Delaunay triangulation of points
on surfaces: the smooth case’. In: Proceedings of the 19th Annual Symposium on Computational
Geometry. 2003, pp. 201–210. DOI: 10.1145/777792.777823. URL: http://dl.acm.org/citati
on.cfm?id=777823.

[30] F. Aurenhammer, R. Klein and D.-T. Lee. Voronoi diagrams and Delaunay triangulations. World

Scientific, 2013. URL: http://www.worldscientific.com/worldscibooks/10.1142/8685.

[31] R. Bardenet, F. Lavancier, X. Mary and A. Vasseur. ‘On a few statistical applications of determinantal
point processes’. In: ESAIM: Procs 60 (2017), pp. 180–202. DOI: 10.1051/proc/201760180. URL:
https://doi.org/10.1051/proc/201760180.

[32] M. Bogdanov, O. Devillers and M. Teillaud. ‘Hyperbolic Delaunay complexes and Voronoi diagrams

made practical’. In: Journal of Computational Geometry 5 (2014), pp. 56–85.

[33] M. Bogdanov, M. Teillaud and G. Vegter. ‘Delaunay triangulations on orientable surfaces of low
genus’. In: Proceedings of the 32nd International Symposium on Computational Geometry. 2016,
20:1–20:15. DOI: 10.4230/LIPIcs.SoCG.2016.20. URL: https://hal.inria.fr/hal-012763
86.

[34]

[35]

J.-D. Boissonnat, O. Devillers and S. Hornus. ‘Incremental construction of the Delaunay graph in
medium dimension’. In: Proceedings of the 25th Annual Symposium on Computational Geometry.
2009, pp. 208–216. URL: http://hal.inria.fr/inria-00412437/.

J.-D. Boissonnat, O. Devillers, R. Schott, M. Teillaud and M. Yvinec. ‘Applications of random
sampling to on-line algorithms in computational geometry’. In: Discrete and Computational Geo-
metry 8 (1992), pp. 51–71. URL: http://hal.inria.fr/inria-00090675.

[36] Y. Bouzidi, S. Lazard, G. Moroz, M. Pouget, F. Rouillier and M. Sagraloff. Improved algorithms for
solving bivariate systems via Rational Univariate Representations. Research Report. INRIA, Feb.
2015. URL: https://hal.inria.fr/hal-01114767.

[37] Y. Bouzidi, S. Lazard, M. Pouget and F. Rouillier. ‘Separating linear forms and Rational Univariate
Representations of bivariate systems’. In: Journal of Symbolic Computation 68 (May 2015), pp. 84–
119. DOI: 10.1016/j.jsc.2014.08.009. URL: https://hal.inria.fr/hal-00977671.

[38] P. Calka. ‘Tessellations, convex hulls and Boolean model: some properties and connections’. Habil-
itation à diriger des recherches. Université René Descartes - Paris V, 2009. URL: https://tel.arc
hives-ouvertes.fr/tel-00448249.

Project GAMBLE

21

[39] M. Caroli, P. M. M. de Castro, S. Loriot, O. Rouiller, M. Teillaud and C. Wormser. ‘Robust and Efficient
Delaunay Triangulations of Points on or Close to a Sphere’. In: Proceedings of the 9th International
Symposium on Experimental Algorithms. Vol. 6049. Lecture Notes in Computer Science. 2010,
pp. 462–473. URL: http://hal.inria.fr/inria-00405478/.

[40] M. Caroli and M. Teillaud. ‘3D Periodic Triangulations’. In: CGAL User and Reference Manual. 3.5.
CGAL Editorial Board, 2009. DOI: 10.1007/978-3-642-04128-0_6. URL: http://doc.cgal.or
g/latest/Manual/packages.html%5C#PkgPeriodic3Triangulation3Summary.

[41] M. Caroli and M. Teillaud. ‘Computing 3D Periodic Triangulations’. In: Proceedings of the 17th
European Symposium on Algorithms. Vol. 5757. Lecture Notes in Computer Science. 2009, pp. 59–
70.

[42] M. Caroli and M. Teillaud. ‘Delaunay Triangulations of Point Sets in Closed Euclidean d -Manifolds’.
In: Proceedings of the 27th Annual Symposium on Computational Geometry. 2011, pp. 274–282. DOI:
10.1145/1998196.1998236. URL: https://hal.inria.fr/hal-01101094.

[43] B. Chazelle et al. ‘Application challenges to computational geometry: CG impact task force report’.
In: Advances in Discrete and Computational Geometry. Ed. by B. Chazelle, J. E. Goodman and R.
Pollack. Vol. 223. Contemporary Mathematics. Providence: American Mathematical Society, 1999,
pp. 407–463.

[44] P. Chossat, G. Faye and O. Faugeras. ‘Bifurcation of hyperbolic planforms’. In: Journal of Nonlinear
Science 21 (2011), pp. 465–498. DOI: 10.1007/s00332-010-9089-3. URL: http://link.spring
er.com/article/10.1007/s00332-010-9089-3.

[45] V. Damerow and C. Sohler. ‘Extreme points under random noise’. In: Proceedings of the 12th
European Symposium on Algorithms. 2004, pp. 264–274. DOI: 10.1007/978-3-540-30140-0_25.
URL: http://dx.doi.org/10.1007/978-3-540-30140-0%5C_25.

[46] O. Devillers. ‘The Delaunay hierarchy’. In: International Journal of Foundations of Computer Science

13 (2002), pp. 163–180. URL: https://hal.inria.fr/inria-00166711.

[47] O. Devillers, M. Glisse and X. Goaoc. ‘Complexity analysis of random geometric structures made
simpler’. In: Proceedings of the 29th Annual Symposium on Computational Geometry. June 2013,
pp. 167–175. DOI: 10.1145/2462356.2462362. URL: https://hal.inria.fr/hal-00833774.

[48] O. Devillers, M. Glisse, X. Goaoc and R. Thomasse. ‘On the smoothed complexity of convex hulls’.
In: Proceedings of the 31st International Symposium on Computational Geometry. Lipics, 2015. DOI:
10.4230/LIPIcs.SOCG.2015.224. URL: https://hal.inria.fr/hal-01144473.

[49] D. Dubhashi and D. Ranjan. ‘Balls and Bins: A Study in Negative Dependence’. In: Random Struc-
tures and Algorithms 13.2 (1998), pp. 99–124. DOI: 10.1002/(SICI)1098-2418(199809)13:2%3
C99::AID-RSA1%3E3.0.CO;2-M.

[50] L. Dupont, D. Lazard, S. Lazard and S. Petitjean. ‘Near-optimal parameterization of the intersection
of quadrics: I. The generic algorithm’. In: Journal of Symbolic Computation 43.3 (2008), pp. 168–191.
DOI: 10.1016/j.jsc.2007.10.006. URL: http://hal.inria.fr/inria-00186089/en.

[51] L. Dupont, D. Lazard, S. Lazard and S. Petitjean. ‘Near-optimal parameterization of the intersection
of quadrics: II. A classification of pencils’. In: Journal of Symbolic Computation 43.3 (2008), pp. 192–
215. DOI: 10.1016/j.jsc.2007.10.012. URL: http://hal.inria.fr/inria-00186090/en.

[52] L. Dupont, D. Lazard, S. Lazard and S. Petitjean. ‘Near-Optimal Parameterization of the Intersection
of Quadrics: III. Parameterizing Singular Intersections’. In: Journal of Symbolic Computation 43.3
(2008), pp. 216–232. DOI: 10.1016/j.jsc.2007.10.007. URL: http://hal.inria.fr/inria-0
0186091/en.

[53] M. Glisse, S. Lazard, J. Michel and M. Pouget. ‘Silhouette of a random polytope’. In: Journal of
Computational Geometry 7.1 (2016), p. 14. URL: https://hal.inria.fr/hal-01289699.

[54] M. Hemmer, L. Dupont, S. Petitjean and E. Schömer. ‘A complete, exact and efficient implement-
ation for computing the edge-adjacency graph of an arrangement of quadrics’. In: Journal of
Symbolic Computation 46.4 (2011), pp. 467–494. DOI: 10 . 1016 / j . jsc . 2010 . 11 . 002. URL:
https://hal.inria.fr/inria-00537592.

22

[55]

Inria Annual Report 2023

J. Hidding, R. van de Weygaert, G. Vegter, B. J. Jones and M. Teillaud. ‘Video: the sticky geometry of
the cosmic web’. In: Proceedings of the 28th Annual Symposium on Computational Geometry. 2012,
pp. 421–422.

[56]

J. B. Hough, M. Krishnapur, Y. Peres and B. Virág. ‘Determinantal processes and independence’. In:
Probab. Surv. 3 (2006), pp. 206–229.

[57] A. Kulesza and B. Taskar. ‘Determinantal Point Processes for Machine Learning’. In: Foundations
and Trends® in Machine Learning 5.2–3 (2012), pp. 123–286. DOI: 10.1561/2200000044. URL:
http://dx.doi.org/10.1561/2200000044.

[58] S. Lazard, L. sM. Peñaranda and S. Petitjean. ‘Intersecting quadrics: an efficient and exact imple-
mentation’. In: Computational Geometry: Theory and Applications 35.1-2 (2006), pp. 74–99.

[59] O. Macchi. ‘The coincidence approach to stochastic point processes’. In: Advances in Applied

Probability 7.1 (1975), pp. 83–122. DOI: 10.2307/1425855.

[60] M. Mazón and T. Recio. ‘Voronoi diagrams on orbifolds’. In: Computational Geometry: Therory and

Applications 8 (1997), pp. 219–230.

[61] A. Pellé and M. Teillaud. Periodic meshes for the CGAL library. International Meshing Roundtable.

Research Note. Londres, United Kingdom, 2014. URL: https://hal.inria.fr/hal-01089967.

[62] A. Rényi and R. Sulanke. ‘Über die konvexe Hülle von n zufällig gerwählten Punkten I’. In: Z.
Wahrsch. Verw. Gebiete 2 (1963), pp. 75–84. DOI: 10.1007/BF00535300. URL: http://dx.doi.or
g/10.1007/BF00535300.

[63] A. Rényi and R. Sulanke. ‘Über die konvexe Hülle von n zufällig gerwählten Punkten II’. In: Z.
Wahrsch. Verw. Gebiete 3 (1964), pp. 138–147. DOI: 10.1007/BF00535973. URL: http://dx.doi
.org/10.1007/BF00535973.

[64] G. Rong, M. Jin and X. Guo. ‘Hyperbolic centroidal Voronoi tessellation’. In: Proceedings of the ACM
Symposium on Solid and Physical Modeling. 2010, pp. 117–126. DOI: 10.1145/1839778.1839795.
URL: http://dx.doi.org/10.1145/1839778.1839795.

[65] F. Sausset, G. Tarjus and P. Viot. ‘Tuning the fragility of a glassforming liquid by curving space’. In:
Physical Review Letters 101 (2008), 155701(1)–155701(4). DOI: 10.1103/PhysRevLett.101.15570
1. URL: http://dx.doi.org/10.1103/PhysRevLett.101.155701.

[66] M. Schindler and A. C. Maggs. ‘Cavity averages for hard spheres in the presence of polydispersity
and incomplete data’. In: The European Physical Journal E (2015), pp. 38–97. DOI: 10.1103/Phys
RevE.88.022315. URL: http://dx.doi.org/10.1103/PhysRevE.88.022315.

[67] D. A. Spielman and S.-H. Teng. ‘Smoothed analysis: why the simplex algorithm usually takes
polynomial time’. In: Journal of the ACM 51 (3 2004), pp. 385–463. DOI: 10.1145/990308.990310.
URL: http://dx.doi.org/10.1145/990308.990310.

[68] M. Teillaud. Towards dynamic randomized algorithms in computational geometry. Vol. 758. Lecture
Notes Comput. Sci. Springer-Verlag, 1993. DOI: 10.1007/3-540-57503-0. URL: http://www.spr
inger.com/gp/book/9783540575030.

[69] R. van de Weygaert, G. Vegter, H. Edelsbrunner, B. J. Jones, P. Pranav, C. Park, W. A. Hellwing, B.
Eldering, N. Kruithof, E. Bos, J. Hidding, J. Feldbrugge, E. ten Have, M. van Engelen, M. Caroli
and M. Teillaud. ‘Alpha, Betti and the megaparsec universe: on the homology and topology of
the cosmic web’. In: Transactions on Computational Science XIV. Vol. 6970. Lecture Notes in
Computer Science. Springer-Verlag, 2011, pp. 60–101. DOI: 10.1007/978-3-642-25249-5_3.
URL: http://dx.doi.org/10.1007/978-3-642-25249-5%5C_3.
<scratchpad>
- Main topic: Research Centre at Inria Centre at Université de Lorraine
- Key points:
  - GAMBLE project-team, focusing on geometric algorithms and models beyond the linear and Euclidean realm
  - Research areas: non-linear computational geometry, non-Euclidean computational geometry, probability in computational geometry, discrete geometric structures
  - Application domains: algorithmics, programming, software and architecture, computer algebra and cryptology
  - Software development: pwpoly, CGAL
- Structure: The document is divided into several sections, including project-team members, activity report, research program, application domains, new software, new results, and partnerships and cooperations
- Potential artifacts to ignore: web-related elements, unnecessary links, and formatting
</scratchpad>

<final_summary>
The GAMBLE project-team at Inria Centre at Université de Lorraine focuses on research in geometric algorithms and models beyond the linear and Euclidean realm. The team's research areas include non-linear computational geometry, non-Euclidean computational geometry, probability in computational geometry, and discrete geometric structures. These areas have significant application domains in algorithmics, programming, software and architecture, computer algebra and cryptology. The team has developed software such as pwpoly and CGAL, which have been used in various fields, including computer-aided design and manufacturing, computer vision, and statistics. The GAMBLE project-team aims to contribute to the development of computational geometry for non-Euclidean spaces and make these developments readily available for users in academia and industry.
The GAMBLE project-team at Inria Centre at Université de Lorraine focuses on research in geometric algorithms and models beyond the linear and Euclidean realm. The team's research areas include non-linear computational geometry, non-Euclidean computational geometry, probability in computational geometry, and discrete geometric structures. These areas have significant application domains in algorithmics, programming, software and architecture, computer algebra and cryptology. The team has developed software such as pwpoly and CGAL, which have been used in various fields, including computer-aided design and manufacturing, computer vision, and statistics. The GAMBLE project-team aims to contribute to the development of computational geometry for non-Euclidean spaces and make these developments readily available for users in academia and industry.