Towards an Algorithmic Understanding of 3-Dimensional Shapes

Orateur : Kristóf Huszár
05 Avril 2022 à 14:00 ; lieu : Seminar room 4B125 (Copernic building)

Kristóf Huszár

Résumé :

Topology – the area of mathematics concerned with the study of shape – has always been interspersed with combinatorial ideas, therefore it is not surprising that many of its fundamental questions call for an algorithmic solution. This is particularly the case in 3-dimensions, where problems such as UNKNOT RECOGNITION (i.e., deciding whether a closed polygonal loop embedded in the Euclidean 3-space is knotted) and 3-SPHERE RECOGNITION (i.e., deciding whether a given triangulation describes the 3-dimensional sphere) have been driven research for over a century.

In this talk we first revisit the historical connection between topology and theoretical computer science. Then we discuss some fixed-parameter tractable algorithms that can efficiently solve hard problems about 3-manifolds, provided the input triangulation is sufficiently « thin. » Finally, we elaborate on the quantitative relationship between the combinatorial parameter that quantifies the « width » of a triangulation, and classical topological invariants of the underlying 3-manifold.

Joint work with Jonathan Spreer and Uli Wagner.


Seminar room 4B125 (Copernic building)

5 Boulevard Descartes 77420 Champs-sur-Marne