Günter Rote - Freie Universität Berlin

Pseudotriangulations, Polytopes, and How to Expand Linkages

Abstract: The carpenter's rule problem asks for a motion that makes a given polygonal chain in the plane straight. This problem has received a positive solution: any polygonal chain consisting of fixed-length bars connected by movable joints (a linkage or framework) can be straightened in the plane without crossing itself.

I will survey proofs of this result and show connections to so-called pseudotriangulations and convex polytopes, covering joint work with Bob Connelly, Erik Demaine, Paco Santos, and Ileana Streinu.

Colloquium - 16:00

Csaba Tóth - ETH Zürich

Illuminating disjoint line segments

Abstract: What is the minimum number of light sources that can illuminate the union L of any family of n disjoint line segments in the plane? Similarly, what is the minimum number of light sources that can illuminate the free space, i.e. the complement of L, for any family of n disjoint segments? Every point in the target set should be illuminated by at least one of the light sources. We show that variants of these problems are related to graph packings with paths of at least three vertices. We can give upper bounds, some of which are tight, on the number of light sources by using a characterization of graphs that can be partitioned into such paths.