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
Search by for:
Upper and Lower Bounds for Connecting Sites Across Barriers
Authors: Krumme, David W.; Perkins, Greg; Rafalin, Eynat; Souvaine, Diane L.
Date:June 2003
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 2n-2. 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.