A Steiner tree related theorem

This entry justifies some of the assumptions behind the algorithm devised at the prior entry "Within 50 km, revisited".

Let C be a finite set of 2D points called cities, and r > 0. The r-coverage problem for C, abbreviated Cov(C,r), consists of finding a set of nodes N and an associated tree T spanning those nodes with the following properties:

• For every c in C there is some n in N such that dist(c,n) ≤ r (coverage property).
  
• The length of T is minimum.
  

It is easy to see that for any solution (N,T) to Cov(C,r) the tree T is the Steiner tree of N, ST(N), so we need only concentrate on finding the set of nodes N. We now prove that, under certain conditions, we can restrict our search for solutions to Cov(C,r) to nodes lying in the r-circles centered at the cities of C.

Definition. A set of cities C is r-separable if for any c in C there is some c' in C such that dist(c,c') ≥ 2r.

Theorem. Let us index the set of cities C as c₁,...,c_m, and let M = {{n₁,...,n_m} : n_i in D(c_i,r)}, where D(c_i,r) is the circle of radius r centered at the point c_i. If C is r-separable, there is a solution (D,ST(D)) to Cov(C,r) such that D belongs to M.

Lemma. Let A be a set of points and B a set of points lying in ST(A). Then, length(ST(B)) ≤ length(ST(A)). Proof. Obviously ST(A+B) = ST(A). Now, from the properties of Steiner trees it follows that if X is a subset oy Y, length(ST(X)) ≤ length(ST(Y)), and as B is a subset of A+B we have length(ST(B)) ≤ length(ST(A+B)) = length(ST(A)).

Proof of theorem. Let (N,ST(N)) be a solution to Cov(C,r). From the r-separability of C, ST(N) must intersect each circle D(c_i,r) at some point d_i; now, if we take (D,ST(D)), where D = {d₁,..,d_m}, it is easy to see that

• D satisfies the coverage property,
  
• by our prior lemma, length(ST(D)) cannot be greater than length(ST(N)),
  

so (D,ST(D)) is a solution to Cov(C,r).