Technical Reports
Display by Author: A
 B
 C
 D
 E
 F
 G
 H
 I
 J
 K
 L
 M
 N
 O
 P
 Q
 R
 S
 T
 U
 V
 W
 X
 Y
 Z
TR20036
Upper and Lower Bounds for Connecting Sites Across Barriers 

Authors:  Krumme, David W.; Perkins, Greg; Rafalin, Eynat; Souvaine, Diane L. 
Date:  June 2003 
Pages:  16 
Download Formats:  [PDF] 
Given a set M of m distinct points (sites) and a set N of n segments (barriers) in the plane, we address the problem of constructing a planar spanning tree of M of straight edges with minimal cost, where the cost function is the number of times that edges cross barriers (the 'crossing number'). For the restricted problem where barriers form a convex planar subdivision and each face contains exactly one site, we prove a tight bound of 5n/3 total cuts. As for the number of cuts per barrier, we prove that at most 3 cuts per barrier are needed, provide a lower bound of 2 cuts per barrier and develop a linear time algorithm. Asano et al. 99 proved upper bounds of 4 cuts per barrier and a total cost of 4n for the general case, with corresponding lower bounds of 2 and 2n2. New constructions developed here may apply both to other problems and to tightening the bounds in the general case. 
Faculty: for help posting a technical report please visit the User Guide.