Frequency-distance constraints with large distances

Journal article

Given a set V of points in the plane, and a vector of distances d = (d0,d1,...,dk-1), an assignment f : V → {1,2,...,t} is called d-feasible if |f(u) - f(v)| > i whenever the distance between the points u and v is less than di. We think of the points in V as sites to which we are to assign radio channels, subject to 'frequency-distance' constraints which ensure that interference is not excessive. The span χ(d; V) is the least t for which there is such an assignment. We investigate the span in the case when the distances are large: specifically, we suppose that d = dx where x = (x0,x1,...,xk-1) is fixed and d → ∞. We find that as d → ∞, the ratio χ(dx; V)/d2 tends to a limit, which is the product of the upper density of V and the 'inverse channel density' χ(x) of x. Also we derive some partial results about the limiting value χ(x): we find for example, that χ(1, 1/√2) = 1 and χ(1,x,x) = √3/2max(1,x2/√3) for each 0≤x≤1. Some of our upper bounds on χ correspond to channel assignment methods that may be of practical interest. © 2000 Elsevier Science B.V. All rights reserved.

Authors: McDiarmid, C

• Publication status: Published
• Journal: DISCRETE MATHEMATICS More from this journal
• Volume: 223
• Issue: 1-3
• Pages: 227-251
• Publication date: 2000-08-28
• DOI: 10.1016/S0012-365X(00)00016-9
• ISSN: 0012-365X
• Language: English