DIMACS TR: 99-34
A Cost Upper Bound for Spanning Trees Connecting Faces
of a Planar Subdivision
Authors: Greg Perkins and Diane Souvaine
ABSTRACT
Let $M$ be a set of $m$ distinct points and $N$ a set of $n$ line
segments in the plane where the relative interiors of all line segments
are disjoint and no $p_i \in M$ lies upon any $s_j \in N$. Define the cost
of a spanning tree $T$ of $M$
as the number of intersections which occur between the edges of $T$
and the line segments of $N$. This paper proves that for any $M$ and $N$ there
always exists a
(non-Steiner) spanning tree $T$ with cost $< 2n - 1$. Furthermore, we show
that
$T$ always exist such that each line segment in $N$ is cut at most twice
by the edges of $T$ and that the $2n-1$ bound is tight.
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1999/99-34.ps.gz
DIMACS Home Page