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.