Frequency-distance constraints with large distances Original Research 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/2 max(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.