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.

Schedule

Talks

Cycles and lenses: Algebraic techniques in discrete geometry

Micha Sharir

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

Uli Wagner

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

Martin Tancer

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 ℝ³

Imre Bárány

We prove that given a finite collection of cylinders in ℝ³ 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