Glimpses into geometry and topology
Miniworkshop on topics in favourite areas of J. Matoušek
Friday Oct 1
J. Matoušek Lecture Hall (N1)
Charles University, Faculty of Mathematics and Physics
Pavilion IMPAKT, V Holešovičkách 2, Praha-Troja
The workshop is intended for a broad CS and mathematics community. It is organized as a part of the festive inauguration of J. Matoušek Lecture Hall. Program and other information about the inauguration can be found in the invitation.
|16:00||Micha Sharir||Cycles and lenses: Algebraic techniques in discrete geometry|
|16:45||Uli Wagner||Topology and the Complexity of Flipping Edge-Labelled Triangulations|
|17:15||Martin Tancer||Interactions of topology and computational complexity|
|17:45||Imre Bárány||Pairwise Intersecting Convex Sets and Cylinders in ℝ3|
Cycles and lenses: Algebraic techniques in discrete geometry
We present recent progress on two seemingly unrelated problems: (i) eliminating depth cycles in a collection of lines or triangles in 3-space, and (ii) cutting a set of curves in the plane into pseudo-segments -- no pair of the connected sub-pieces intersect more than once. We show that the two problems are in fact closely related, and derive the same bound on the number of required cuts in both setups. The cycle elimination problem comes from computer graphics, and the curve cutting problem has applications in deriving sharp bounds on incidences between points and curves in the plane, which we also discuss.
Topology and the Complexity of Flipping Edge-Labelled Triangulations
Given a triangulation of a point set P in the plane, an edge flip deletes an edge e of the triangulation whose removal creates a convex quadrilateral, and replaces e by the opposite diagonal of the quadrilateral. It is well-known that any two triangulations of P can be transformed into one another by a finite sequence of such flips.
What happens if each edge of a triangulation has a label, and a flip transfers the label of the removed edge to the new edge? In this setting it is no longer true that any two edge-labeled triangulations can be transformed into one another by a sequence of flips. In this talk, we will explain how to use topology to obtain a characterization of when this is possible (which in turn leads to a polynomial-time decision algorithm). This proves a conjecture of Bose, Lubiw, Pathak and Verdonschot.
Joint work with Anna Lubiw and Zuzana Masárová
Interactions of topology and computational complexity
When I was a PhD student, a major influence of Jirka Matousek was that he taught me to think algorithmically about topological problems. In the first part of the talk I will briefly survey a few such problems including the algorithmic embeddability problem. In the second part of the talk, I will touch in a bit more detail one particular problem: parametrized complexity of untangling (un)knots on which I have been recently working with Clément Legrand-Duchesne and Ashutosh Rai.
Pairwise Intersecting Convex Sets and Cylinders in ℝ3
We prove that given a finite collection of cylinders in ℝ3 with the property that any two them intersect, there is a line intersecting
an α fraction of the cylinders where α = 1/14. This is a special case of an interesting conjecture.
Organizers: Jan Kratochvíl, Helena Nyklová, Pavel Valtr