ICS Theory Group

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.