Computational Geometry

Department of Computer Science

Tight Bounds on the Crossing Number in
an Arrangement of Points and Segments

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 then there is
a spanning tree where every barrier is crossed by O(sqrt{m}) tree
edges (connectors), and this bound is asymptotically optimal (*spanning tree with low stabbing number*). 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*. Constructions with *3*
crossings per barrier and *2n* total cost provide a lower bound.

We obtain tight bounds on the minimum cost spanning tree in the most
exciting special case where the barriers are interior disjoint line
segments that form a convex subdivision and there is a point in
every cell. In particular, we show that there is a spanning tree
such that every barrier is crossed by at most *2* tree edges, and
there is a spanning tree of total cost *5n/3*. Both bounds are
tight.

Example

The Honey-comb: an example of the worst case lower bound for the global crossing number (5/3n) and the crossing number per segment (at most 2 crossings)

Papers

[1] "

Tight Bounds for Connecting Sites Across Barriers", D. Krumme, E. Rafalin, D. Souvaine and C. Toth, submitted for publication ACM SoCG[2] "

Upper and Lower Bounds for Connecting Sites Across Barriers", D. Krumme, G. Perkins, E. Rafalin, D. Souvaine, TUFTS-CS Technical Report, TR-2003-6, Tufts University[3] "

Spanning trees with low crossing number",J. Matousek,RAIRO Inform. Theor. Appl., 25 (2), 1991, pages 103-123[4] "

Spanning trees crossing few barriers",T. Asano, M. de Berg, O. Cheong, L. Guibas,J. Snoeyink, and H. Tamaki,Proc. of the 15th Annual Symp. on Comput. Geom., pages 41-48[5] "

Connecting Points in the Presence of Obstacles in the Plane", Michael Hoffmann and Csaba D. Toth,Proc. of the 14th Canad. Conf. on Comput. Geom., pages 63-67