Tight Bounds for Connecting Sites Across Barriers |
| |
Authors: | David Krumme Eynat Rafalin Diane L Souvaine Csaba D Tóth |
| |
Institution: | (1) Department of Computer Science, Tufts University, Medford, MA 02155, USA;(2) Google Inc., Mountain View, CA 94043, USA;(3) Department of Mathematics, University of Calgary, Calgary, Canada |
| |
Abstract: | Given m points (sites) and n obstacles (barriers) in the plane, we address the problem of finding a straight line minimum cost spanning tree on the sites, where the cost
is proportional to the number of intersections (crossings) between tree edges and barriers. If the barriers are infinite lines,
it is known that there is a spanning tree such that every barrier is crossed by
tree edges, and this bound is asymptotically optimal. Asano et al. showed that if the barriers are pairwise disjoint line
segments, then there is a spanning tree such that every barrier crosses at most 4 tree edges and so the total cost is at most 4n. Lower bound constructions are known with 3 crossings per barrier and 2n total cost.
We obtain tight bounds on the minimum cost of spanning trees in the special case where the barriers are interior disjoint
line segments that form a convex subdivision of the plane and there is a point in every cell of the subdivision. In particular,
we show that there is a spanning tree such that every barrier crosses at most 2 tree edges, and there is a spanning tree of
total cost 5n/3. Both bounds are the best possible.
Work by Eynat Rafalin and Diane Souvaine was supported by the National Science Foundation under Grant #CCF-0431027.
E. Rafalin’s research conducted while at Tufts University. |
| |
Keywords: | Crossing number Spanning trees |
本文献已被 SpringerLink 等数据库收录! |
|