|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.
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 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.
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
Summer break - no seminar in July and August
January 29 - 31, 2020, LuxembourgLost in Translation Surfaces
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.
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
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
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).
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).
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).
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).
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
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
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).
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).
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).