Low-interference networks in metric spaces of bounded doubling dimension

Let S be a set of n points in a metric space, let R={Rp:p∈S} be a set of positive real numbers, and let GR be the undirected graph with vertex set S in which {p,q} is an edge if and only if |pq|⩽min(Rp,Rq). The interference of a point q of S is defined to be the number of points p∈S∖{q} with |pq|⩽Rp. For the case when S is a subset of the Euclidean space Rd, Halldórsson and Tokuyama have shown how to compute a set R such that the graph GR is connected and the maximum interference of any point of S is 2O(d)(1+log(R/D)), where D is the closest-pair distance in S and R is the maximum length of any edge in a minimum spanning tree of S. In this paper, it is shown that the same result holds in any metric space of bounded doubling dimension. Moreover, it is shown that such a set can be computed in expected time. It is shown, by an example of a metric space of doubling dimension one, that the upper bound on the maximum interference is optimal. In fact, this example shows that the maximum interference can be as large as n−1; in contrast, Halldórsson and Tokuyama have shown that, in Rd where d⩾1 is a constant, there always exists a set R such that GR is connected and each point has interference o(n2).