SoS - Structures on Surfaces

  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).  

Starting date: April 1st, 2018.
Duration: 4 years.
End date: Mars 31st, 2022 + 6 months extension due to Covid-19

[Participants] - [Seminar] - [Workshops] - [Publications] - [Positions] - intranet


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 academy and industry.

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

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

Concerning the closely related notions of Delaunay triangulations and circle packings, we intend to study the cases of non-compact surfaces and general hyperbolic surfaces. We will explore the possibility to unify their study and to design algorithms for surfaces equipped with a complex projective structure. We will study isometric embeddings into Euclidean spaces of a cell complex endowed with a compatible metric structure.

In the area of combinatorial structures on surfaces and moduli spaces, we intend to develop efficient algorithms in coordination with a deeper understanding of the core objects. For example, we will consider shortest graphs with given topological properties on a given surface and shortest paths between triangulations. Moreover we also intend to improve the mathematical understanding of the relations between combinatorial structures such as curve, pants and flips graphs and related continuous objects such as Teichmüller and moduli spaces. We have ambitious mathematical goals (such as proving expander type properties for moduli spaces and their combinatorial analogues) as well as plans for software which will allow us to discover new directions of research.





(Virtual) Seminar

One Friday each month. The format is as follows:
13:30 - 14:00 (CET) connexion and informal chat
14:00 - 14:30 SoS Speaker
14:30 - 14:45 Questions / Discussion
14:45 (or earlier) External Speaker
then Questions / Discussion
The link for the connexion will be sent by email

4th Seminar: March 19, 2021

SoS Speaker: TBA.
External Speaker:
Larry Guth (Dept. of Mathematics, MIT).
Shifted schedule:
14:45 - 15:15 (CET) connexion and informal chat
15:15 - 15:45 SoS Speaker
15:45 - 16:00 Questions / Discussion
16:00 External Speaker
then Questions / Discussion

3rd Seminar: February 12, 2021

SoS Speaker: Alba Málaga.
External Speaker: Erin Wolf Chambers (Dept. of Computer Science, Saint Louis University).
Slightly modified schedule:
13:30 - 14:00 (CET) connexion and informal chat
14:00 - 14:30 SoS Speaker
14:30 - 14:45 External Speaker and Questions / Discussion
Then questions / discussion on the SoS talk

2nd Seminar: January 15, 2021

SoS Speaker: Mélanie Theillière. Corrugations and Isometric Embeddings
External Speaker: Richard Evan Schwartz (Dept. of Mathematics, Brown University). Paper Moebius band

1st Seminar: December 11, 2020

SoS Speaker: Arnaud de Mesmay. Contractibility on 3-manifold boundaries and compressed problems on surfaces
External Speaker: Anna Lubiw (David R. Cheriton School of Computer Science, University of Waterloo). Piece-wise Linear Morphing


November 13, 2020 (virtual workshop)

(each talk is followed by 10 min questions / discussion)

09:00 - 09:30 connexion and informal chat
09:30 - 10:00 Thi Hanh Vo. Short closed geodesics on cusped hyperbolic surfaces
10:10 - 10:40 Zili Wang. Flips on Planar Polygons
10:50 - 11:20 Benedikt Kolbe. Equivariant crystallographic tilings of the plane
11:30 - 12:00 SoS discussion, plans for future, etc

July 6 - 7, 2020 (virtual workshop)

Monday Morning (July 6)
09:30 - 10:00 Wayne Lam. Deformation Space of Circle Patterns
10:15 - 10:45 Vincent Despré. Flipping Geometric Triangulations on Hyperbolic Surfaces
10:45 - 11:15 Questions / Coffee break
11:15 - 11:45 Lionel Pournin. Primitive Point Packing

Tuesday Afternoon (July 7)
14:30 - 15:00 Benedikt Kolbe. Delaunay Triangulations on hyperbolic orbifolds
15:15 - 15:45 Binbin Xu. Equivalent Curves on Surfaces
15:45 - 16:15 Questions / Coffee break
16:15 - 16:45 Alfredo Hubard. Filling Areas, Lozenge Tilings, and Discrete Injective Hulls

January 29 - 31, 2020, Luxembourg

Lost in Translation Surfaces

November 20 - 21, 2018, Luxembourg


Kick-off meeting: May 3 - 4, 2018, Nancy




To appear
The vertices of primitive zonotopes. A. Deza, L. Pournin, and R. Rakotonarivo. Contemporary Mathematics.
A Near-Linear Approximation Scheme for Multicuts of Embedded Graphs with a Fixed Number of Terminals. Vincent Cohen-Addad, Éric Colin de Verdière and Arnaud de Mesmay. SIAM Journal of Computing.
Weakly Inscribed Polyhedra. Hao Chen and Jean-Marc Schlenker. Transactions of the American Mathematical Society, Series B.
Quadratic differentials and circle patterns on complex projective tori. W. Y. Lam. Geometry & Topology.

Embeddability of arrangements of pseudocircles on surfaces. Éric Colin de Verdière, Carolina Medina, Edgardo Roldán-Pensado, and Gelasio Salazar. Discrete & Computational Geometry , 64, 386-395, (2020). doi
The diameter of lattice zonotopes. A. Deza, L. Pournin, and N. Sukegawa. Proceedings of the American Mathematical Society 148(8), 3507-3516 (2020). doi
Elementary moves on lattice polytopes. J. David, L. Pournin, and R. Rakotonarivo. Journal of Combinatorial Theory A 172, 105200 (2020). doi
Distance between vertices of lattice polytopes. A. Deza, A. Deza, Z. Guan, and L. Pournin. Optimization Letters 14, 309-326 (2020). doi
Geometric simplicial embeddings of arc-type graphs. Hugo Parlier, Ashley Weber. Journal of the Korean Mathematical Society 57(5), 1103-1118 (2020). doi

Diameter, decomposability, and Minkowski sums of polytopes. A. Deza and L. Pournin. Canadian Mathematical Bulletin 62(4), 741-755 (2019). doi
Eccentricities in the flip-graphs of convex polygons. L. Pournin. Journal of Graph Theory 92(2), 111-129 (2019). doi

Conference Proceedings

Tightening Curves on Surfaces Monotonically with Applications. Hsien-Chih Chang and Arnaud de Mesmay. Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, (2020) doi
Flipping Geometric Triangulations on Hyperbolic Surfaces. Vincent Despré, Jean-Marc Schlenker, and Monique Teillaud. Proceedings 36th International Symposium on Computational Geometry, 35:1-35:16 (2020). doi
Generalizing CGAL Periodic Delaunay Triangulations. Georg Osang, Mael Rouxel-Labbé, and Monique Teillaud. Proceedings 28th European Symposium on Algorithms, 75:1-75:17, (2020). (Best Paper Award - Track B: Engineering and Applications). doi

Almost Tight Lower Bounds for Hard Cutting Problems in Embedded Graphs. Vincent Cohen-Addad, Éric Colin de Verdière, Daniel Marx, Arnaud de Mesmay. Proceedings 35th International Symposium on Computational Geometry, 27:1--27:16 (2019). (Best Paper Award). doi

Embedding graphs into two-dimensional simplicial complexes. Éric Colin de Verdière, Thomas Magnard, and Bojan Mohar. Proceedings 34th International Symposium on Computational Geometry, 27:1-27:14, (2018). doi


2D Hyperbolic Delaunay Triangulations. Mikhail Bogdanov, Iordan Iordanov, and Monique Teillaud. CGAL User and Reference Manual, 4.14 edition (2019). source code on github
2D Periodic Hyperbolic Triangulations. Iordan Iordanov and Monique Teillaud. CGAL User and Reference Manual, 4.14 edition (2019). source code on github

Preprints, Talks at Workshops or at Conferences without formal Proceedings, etc

Deciding when two curves are of the same type. Juan Souto, Thi Hanh Vo. (2020).
Towards a combinatorial algorithm for the enumeration of isotopy classes of tilings on hyperbolic surfaces. Benedikt Kolbe. (2020).
Tile-transitive tilings of the Euclidean and hyperbolic planes by ribbons. Benedikt Kolbe, Vanessa Robins. (2020).
Minimal Delaunay triangulations of hyperbolic surfaces. Matthijs Ebbens, Hugo Parlier, Gert Vegter. (2020).
Delaunay triangulations of generalized Bolza surfaces. Matthijs Ebbens, Iordan Iordanov, Monique Teillaud, Gert Vegter. (2020).
Half-minimizers and Delaunay triangulations on closed hyperbolic surfaces. Vincent Despré, Benedikt Kolbe, Monique Teillaud. (2020).
CMC-1 surfaces via osculating Möbius transformations between circle patterns. W. Y. Lam. (2020).
Systoles and diameters of hyperbolic surfaces. Florent Balacheff, Vincent Despré, Hugo Parlier. (2020).
Measuring pants. Nhat Minh Doan, Hugo Parlier, Ser Peow Tan. (2020).
Polytopal balls arising in optimization. A. Deza, J.-B. Hiriart-Urruty, and L. Pournin. (2020).
Enumerating tilings of triply-periodic minimal surfaces with rotational symmetries. Benedikt Kolbe, Myfanwy Evans. 36th European Workshop on Computational Geometry. (2020).
Triangulations in CGAL: to non-Euclidean spaces... and Beyond! Monique Teillaud. 36th European Workshop on Computational Geometry (Invited talk), (2020).

Short closed geodesics on cusped hyperbolic surfaces. Hanh Vo. (2019).
Delaunay triangulations of symmetric hyperbolic surfaces. Matthijs Ebbens, Iordan Iordanov, Monique Teillaud, and Gert Vegter. 35th European Workshop on Computational Geometry, 15:1-15:8 (2019).

Quantifying the sparseness of simple geodesics on hyperbolic surfaces. Peter Buser, Hugo Parlier. (2018).
Minimal length product over homology bases of manifolds. Florent Balacheff, Steve Karam, Hugo Parlier. (2018).
Delaunay Triangulations of Points on Circles. Vincent Despré, Olivier Devillers, Hugo Parlier, Jean-Marc Schlenker. (2018).
Delaunay triangulations of regular hyperbolic surfaces (abstract). Matthijs Ebbens, Iordan Iordanov, Monique Teillaud, and Gert Vegter. 9th International Conference on Curves and Surfaces. (2018).
Systole of regular hyperbolic surfaces with an application to Delaunay triangulations (abstract). Matthijs Ebbens, Iordan Iordanov, Monique Teillaud, and Gert Vegter. 9th International Conference on Curves and Surfaces. (2018).


Last modified: Tue Jan 19 10:22:43 CET 2021