×

Frequency-distance constraints with large distances. (English) Zbl 1015.90021

Summary: Given a set \(V\) of points in the plane, and a vector of distances \({\mathbf d}=(d_0, d_1,\dots, d_{k-1})\), an assignment \(f: V\to \{1,2,\dots, t\}\) is called \({\mathbf d}\)-feasible if \(|f(u)- f(v)|> i\) whenever the distance between the points \(u\) and \(v\) is less than \(d_i\). We think of the points in \(V\) as sites to which we are to assign ratio channels, subject to ‘frequency-distance’ constraints which ensure that interference is not excessive. The span \(\chi({\mathbf d};V)\) is the least \(t\) for which there is such an assignment. We investigate the span in the case when the disances are large: specifically, we suppose that \({\mathbf d}= d{\mathbf x}\) where \({\mathbf x}= (x_0,x_1,\dots, x_{k-1})\) is fixed and \(d\to\infty\). We find that as \(d\to\infty\), the ratio \(\chi(d{\mathbf x};V)/d^2\) tends to a limit, which is the product of the upper density of \(V\) and the ‘inverse channel density’ \(\chi({\mathbf x})\) of \({\mathbf x}\). Also we derive some partial results about the limiting value \(\chi({\mathbf x})\): we find for example that \(\chi(1,1/\sqrt{2})= 1\) and \(\chi(1,x,x)= \sqrt{3}/2\max(1, x^2/\sqrt{3})\) for each \(0\leq x\leq 1\). Some of our upper bounds on \(\chi\) correspond to channel assignment methods that may be of practical interest.

MSC:

90B18 Communication networks in operations research
05C35 Extremal problems in graph theory
Full Text: DOI