# ICS 269, Fall 2003: Theory Seminar

## 21 Nov 2003:

Spanning Trees Crossing Few Barriers

authored by Tetsuo Asano, Mark de Berg, Otfried Cheong, Leonidas J. Guibas,
Jack Snoeyink, Hisao Tamaki

In: 15th Annual Symposium on Computational Geometry (SCG '99).
###
presented by Jeremy Yu Meng

They consider the problem of finding low-cost spanning trees for sets
of *n* points in the plane,
where the cost of a spanning tree is defined as the
total number of intersections of tree edges with a given set of
*m* barriers.