Geometric Spanners For Compact Regions

Let R be a set of n pairwise disjoint compact path connected subsets of the plane. We refer to the elements of R as regions. We suppose that travelling inside each of these regions is free, whereas the cost of travelling outside these regions corresponds to the travelled distance. This gives rise to a metric space (R, delta(T)) where T corresponds to the most cost-effective graph connecting the regions of R and delta(T) corresponds to the length of a shortest path in T. We show that T can be approximated by two cone based algorithms: the first algorithm, based on Yao graphs, yields a graph whose spanning ratio is 1/(1-sin(theta/2) and the second, based on theta graphs, yields a graph whose spanning ratio is (1/(cos theta - sin theta. We also show that T can be approximated by a greedy algorithm when the regions are assumed to be "fat".