Frequency-distance constraints with large distances
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 ra...
| Main Author: | |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
2000
|
| _version_ | 1826265984083689472 |
|---|---|
| author | McDiarmid, C |
| author_facet | McDiarmid, C |
| author_sort | McDiarmid, C |
| collection | OXFORD |
| description | 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. |
| first_indexed | 2024-03-06T20:32:05Z |
| format | Journal article |
| id | oxford-uuid:31641187-eef5-4587-ad13-74772c23492f |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-06T20:32:05Z |
| publishDate | 2000 |
| record_format | dspace |
| spelling | oxford-uuid:31641187-eef5-4587-ad13-74772c23492f2022-03-26T13:07:39ZFrequency-distance constraints with large distancesJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:31641187-eef5-4587-ad13-74772c23492fEnglishSymplectic Elements at Oxford2000McDiarmid, CGiven 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. |
| spellingShingle | McDiarmid, C Frequency-distance constraints with large distances |
| title | Frequency-distance constraints with large distances |
| title_full | Frequency-distance constraints with large distances |
| title_fullStr | Frequency-distance constraints with large distances |
| title_full_unstemmed | Frequency-distance constraints with large distances |
| title_short | Frequency-distance constraints with large distances |
| title_sort | frequency distance constraints with large distances |
| work_keys_str_mv | AT mcdiarmidc frequencydistanceconstraintswithlargedistances |