Disjoint Compatible Geometric Matchings
Speaker:
Csaba Toth, University of Oxford
Date and Time:
Tuesday, September 13, 2011 - 2:00pm to 3:00pm
Abstract:
We prove that for every even set of n pairwise disjoint line segments in the plane in general position, there is another set of n segments such that the 2n segments form pairwise disjoint simple polygons in the plane. This settles in the affirmative the Disjoint Compatible Matching Conjecture by Aichholzer et al.. The key tool in our proof is a novel subdivision of the free space around n disjoint line segments into at most n+1 convex cells such that the dual graph of the subdivision contains two edge-disjoint spanning trees. (Joint work with Mashhood Ishaque and Diane Souvaine).