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.