SoS is cofunded by ANR (ANR17CE400033) and FNR (INTER/ANR/16/11554412/SoS) as a PRCI (Projet de Recherche Collaborative Internationale). 
Starting date: April 1st, 2018.
Duration: 4 years
+
6 months automatic extention
+ 6 months additional extension, due to the Covid19 pandemic.
End date: March 31st, 2022 March 31st, 2023.
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 longterm 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 nonEuclidean geometries are arising, e.g., in geometric modeling, neuromathematics, or physics. Our goal is to develop computational geometry for some of these nonEuclidean 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 longerterm 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 noncompact 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.
Inria, Loria

LIGM

RMATH


One Friday each month.
The usual 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 External Speaker
then Questions / Discussion
The link for the connexion will be sent by email
January 29  31, 2020, LuxembourgLost in Translation Surfaces 
To appear
Tightening Curves on Surfaces Monotonically with Applications.
HsienChih Chang and Arnaud de Mesmay.
ACM Transactions on Algorithms.
Weakly Inscribed Polyhedra.
Hao Chen and JeanMarc Schlenker.
Transactions of the American Mathematical Society, Series B.
2022
Algorithms for Contractibility of Compressed Curves on 3Manifold Boundaries.
Erin Wolf Chambers, Francis Lazarus, Arnaud de Mesmay, and Salman Parsa.
Discrete & Computational Geometry. 132 (2022).
doi
Delaunay triangulations of generalized Bolza surfaces.
Matthijs Ebbens, Iordan Iordanov, Monique Teillaud, Gert Vegter.
Journal of Computational Geometry. 13(1), 125177 (2022).
2021
The minimal length product over homology bases of manifolds.
Florent Balacheff, Steve Karam, and Hugo Parlier.
Mathematische Annalen, 380, 825–854 (2021).
doi
A NearLinear Approximation Scheme for Multicuts of Embedded Graphs with a Fixed Number of Terminals.
Vincent CohenAddad, Éric Colin de Verdière, and Arnaud de Mesmay.
SIAM Journal of Computing, 50(1), 1–31, (2021).
doi
Almost Tight Lower Bounds for Hard Cutting Problems in Embedded Graphs.
Vincent CohenAddad, Éric Colin de Verdière, Dániel Marx, and Arnaud de Mesmay.
J. ACM, 68(4), 30:130:26, (2021).
doi
The vertices of primitive zonotopes.
A. Deza, L. Pournin, and R. Rakotonarivo.
AMS Special Session Polytopes and Discrete Geometry. Contemporary Mathematics, 764, 7182, (2021).
doi
Quadratic differentials and circle patterns on complex projective tori.
W. Y. Lam.
Geometry & Topology, 25(2), 961997, (2021).
doi
2020
Embeddability of arrangements of pseudocircles on surfaces.
Éric Colin de Verdière, Carolina Medina, Edgardo RoldánPensado, and Gelasio Salazar.
Discrete & Computational Geometry, 64, 386395, (2020).
doi
The diameter of lattice zonotopes.
A. Deza, L. Pournin, and N. Sukegawa.
Proceedings of the American Mathematical Society 148(8), 35073516
(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, 309326 (2020).
doi
Geometric simplicial embeddings of arctype graphs.
Hugo Parlier, Ashley Weber.
Journal of the Korean Mathematical Society 57(5), 11031118 (2020).
doi
2019
Diameter, decomposability, and Minkowski sums of polytopes.
A. Deza and L. Pournin.
Canadian Mathematical Bulletin 62(4), 741755 (2019).
doi
Eccentricities in the flipgraphs of convex polygons.
L. Pournin.
Journal of Graph Theory 92(2), 111129 (2019).
doi
2022
Finding Weakly Simple Closed Quasigeodesics on Polyhedral Spheres
Jean Chartier and Arnaud de Mesmay.
Proceedings 38th International Symposium on Computational Geometry, 27:127:16 (2022)
Short Topological Decompositions of NonOrientable Surfaces.
Niloufar Fuladi, Alfredo Hubard, and Arnaud de Mesmay.
Proceedings 38th International Symposium on Computational Geometry, 41:141:16 (2022)
2021
Algorithms for Contractibility of Compressed Curves on 3Manifold Boundaries.
Erin Wolf Chambers, Francis Lazarus, Arnaud de Mesmay, and Salman Parsa.
Proceedings 37th International Symposium on Computational Geometry, 23:123:16, (2021).
Minimal Delaunay triangulations of hyperbolic surfaces.
Matthijs Ebbens, Hugo Parlier, Gert Vegter.
Proceedings 37th International Symposium on Computational Geometry, 31:131:16, (2021).
An FPT Algorithm for the Embeddability of Graphs into TwoDimensional Simplicial Complexes.
Éric Colin de Verdière and Thomas Magnard.
Proceedings 29th European Symposium on Algorithms, 32:132:17, (2021).
2020
Tightening Curves on Surfaces Monotonically with Applications.
HsienChih Chang and Arnaud de Mesmay.
Proceedings of the ACMSIAM Symposium on Discrete Algorithms, (2020).
doi
Flipping Geometric Triangulations on Hyperbolic Surfaces.
Vincent Despré, JeanMarc Schlenker, and Monique Teillaud.
Proceedings 36th International Symposium on Computational Geometry, 35:135:16 (2020).
Generalizing CGAL Periodic Delaunay Triangulations.
Georg Osang, Mael RouxelLabbé, and Monique Teillaud.
Proceedings 28th European Symposium on Algorithms, 75:175:17, (2020).
(Best Paper Award  Track B: Engineering and Applications).
2019
Almost Tight Lower Bounds for Hard Cutting Problems in Embedded Graphs.
Vincent CohenAddad, Éric Colin de Verdière, Daniel Marx, Arnaud de Mesmay.
Proceedings 35th International Symposium on Computational Geometry, 27:127:16 (2019).
(Best Paper Award).
2018
Embedding graphs into twodimensional simplicial complexes.
Éric Colin de Verdière, Thomas Magnard, and Bojan Mohar.
Proceedings 34th International Symposium on Computational Geometry, 27:127:14,
(2018).
2021
2D Triangulations on the Sphere.
Mael RouxelLabbé, Monique Teillaud, and Claudia Werner.
CGAL User and Reference Manual, 5.3 edition (2021).
source code on github
2019
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
2022
A bound for Delaunay flip algorithms on flat tori.
Loïc Dubois.
(Best student paper) Canadian Conference on Computational Geometry, Aug 2022, Toronto, Canada.
(2022).
Experimental analysis of Delaunay flip algorithms on genus two hyperbolic surfaces.
Vincent Despré, Loïc Dubois, Benedikt Kolbe, and Monique Teillaud.
38th European Workshop on Computational Geometry.
(2022).
The coarse geometry of hexagon decomposition graphs
Funda Gültepe, Hugo Parlier.
(2022).
2021
Experimental analysis of Delaunay flip algorithms on genus two hyperbolic surfaces
Vincent Despré, Loïc Dubois, Benedikt Kolbe, and Monique Teillaud.
(2021).
Strong convexity in flipgraphs
Lionel Pournin and Zili Wang.
(2021).
Holonomic approximation through convex integration
Patrick Massot, Mélanie Theillière.
(2021).
2020
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).
Tiletransitive 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).
Halfminimizers and Delaunay triangulations on closed hyperbolic surfaces.
Vincent Despré, Benedikt Kolbe, Monique Teillaud.
(2020).
CMC1 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. HiriartUrruty, and L. Pournin.
(2020).
Enumerating tilings of triplyperiodic minimal surfaces with rotational symmetries.
Benedikt Kolbe, Myfanwy Evans.
36th European Workshop on Computational Geometry.
(2020).
Triangulations in CGAL: to nonEuclidean spaces... and Beyond!
Monique Teillaud.
(Invited talk) 36th European Workshop on Computational Geometry.
(2020).
2019
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.
(2019).
2018
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, JeanMarc 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).