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 + 6 months automatic extention + 6 months additional extension, due to the Covid-19 pandemic.
End date: March 31st, 2022 March 31st, 2023.

Abstract

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.

Participants

Sites

• Gamble project-team, Inria (Institut National de Recherche en Informatique et Automatique), Research Center Nancy - Grand Est, Loria
• LIGM (Laboratoire d'Informatique Gaspard Monge), Université Paris-Est Marne-la-Vallée
• RMATH (Mathematics Research Unit), University of Luxembourg

Members

(Virtual) Seminar

6th Seminar: June 25, 2021

5th Seminar: May 28, 2021

4th Seminar: March 19, 2021

3rd Seminar: February 12, 2021

2nd Seminar: January 15, 2021

1st Seminar: December 11, 2020

Workshops

May 2 - 6, 2022 - Workshop at CIRM

November 13, 2020 (virtual workshop)

July 6 - 7, 2020 (virtual workshop)

January 29 - 31, 2020, Luxembourg Lost in Translation Surfaces

November 20 - 21, 2018, Luxembourg

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

Publications

Journals

To appear
Delaunay triangulations of generalized Bolza surfaces. Matthijs Ebbens, Iordan Iordanov, Monique Teillaud, Gert Vegter. Journal of Computational Geometry.
Weakly Inscribed Polyhedra. Hao Chen and Jean-Marc Schlenker. Transactions of the American Mathematical Society, Series B.

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 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, 50(1), 1–31, (2021). doi
Almost Tight Lower Bounds for Hard Cutting Problems in Embedded Graphs. Vincent Cohen-Addad, Éric Colin de Verdière, Dániel Marx, and Arnaud de Mesmay. J. ACM, 68(4), 30:1-30: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, 71-82, (2021). doi
Quadratic differentials and circle patterns on complex projective tori. W. Y. Lam. Geometry & Topology, 25(2), 961-997, (2021). doi

2020
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

2019
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

2021
Algorithms for Contractibility of Compressed Curves on 3-Manifold Boundaries. Erin Wolf Chambers, Francis Lazarus, Arnaud de Mesmay, and Salman Parsa. Proceedings 37th International Symposium on Computational Geometry, 23:1--23:16, (2021).
Minimal Delaunay triangulations of hyperbolic surfaces. Matthijs Ebbens, Hugo Parlier, Gert Vegter. Proceedings 37th International Symposium on Computational Geometry, 31:1--31:16, (2021).
An FPT Algorithm for the Embeddability of Graphs into Two-Dimensional Simplicial Complexes. Éric Colin de Verdière and Thomas Magnard. Proceedings 29th European Symposium on Algorithms, 32:1-32:17, (2021).

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

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

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

Software

2021
2D Triangulations on the Sphere. Mael Rouxel-Labbé, 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

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

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 flip-graphs 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).
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).
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. (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, 15:1-15:8 (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, 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).

Positions

• CLOSED - One-year postdoctoral position in Nancy
• CLOSED - One-year postdoctoral position in Marne-la-Vallée
• CLOSED - 18-months postdoctoral position in Luxembourg