Let S be a set of n points in a metric space, let R={R p: pεS} be a set of positive real numbers, and let R R be the undirected graph with vertex set S in which {p,q} is an edge if and only if |pq|≤min(R p,R q). The interference of a point q of S is defined to be the number of points pεS/{q} with |pq|≤R p. For the case when S is a subset of the Euclidean space R d, Halldórsson and Tokuyama have shown how to compute a set R such that the graph R R is connected and the maximum interference of any point of S is 2 O(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 O(nlogn) 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 R d where d≥1 is a constant, there always exists a set R such that R R is connected and each point has interference o( n2).

Additional Metadata
Keywords Algorithms, Doubling dimension, Interference, Metric space, Minimum spanning tree, Spanner, Wireless networks
Persistent URL dx.doi.org/10.1016/j.ipl.2011.09.013
Journal Information Processing Letters
Citation
Maheshwari, A, Smid, M, & Zeh, N. (Norbert). (2011). Low-interference networks in metric spaces of bounded doubling dimension. Information Processing Letters, 111(23-24), 1120–1123. doi:10.1016/j.ipl.2011.09.013