Speaker: Csaba D. Toth


TITLE: Plane partitions for disjoint line segments

ABSTRACT:
A binary space partition (BSP) for n line segments in the plane is a 
recursive partition scheme that
partitions the plane along a line, and recurses on the segments clipped 
in each open halfplane until
every subproblem is empty. Sometimes it is inevitable that a partition 
line crosses some of the line
segments. There are n disjoint segments which are partitioned into 
Omega(n log n/ log log n) fragments
by any BSP. It is shown that this lower bound is best possible apart 
from the constant factor.

The free space around n disjoint line segments can be decomposed into 
n+1 convex faces, and sometimes
there is no convex decomposition with fewer than n+1 faces. Define a 
dual graph on a decomposition:
let the convex faces correspond to nodes, and let every segment endpoint 
correspond to an edge between
two incident convex faces. Aichholzer and others conjectured that for n 
segments there is a convex
decomposition into n+1 faces such that the dual graph is the union of 
two spanning trees. It is shown that
n segments admit a convex decomposition into n+1 faces such that the 
dual graph is 2-edge connected.