Centre for Discrete and Applicable Mathematics

 CDAM Research Report, LSE-CDAM-98-05

March 1998

Radio Channel Assignment on 2-Dimensional Lattices

J. van den Heuvel


Given a set  V  of points in the plane, a sequence  d0,d1, . . . ,dk  of non-negative numbers and an integert  n,  we are interested in the problem to assign integers from  {0, . . . ,n-1}  to the points in  V  such that if  xy in V  are two points with euclidean distance less than  di,  then the difference between the labels of  x  and  y  is not equal to  i.  This question is inspired by problems occurring in the design of radio networks, where radio channels need to be assigned to transmitters in such a way that interference is minimised. In this paper we consider the case that the set of points are the points of a 2-dimensional lattice. Recent results by McDiarmid and Reed show that if only one constraint  d0  is given, good labellings can be obtained by using so-called strict tilings. We extend these results to the case that higher level constraints  d0,d1, . . . ,dk  occur. In particular we study conditions that guarantee that a strict tiling, satisfying only the one constraint  d0,  can be transformed to a strict tiling satisfying the higher order constraints as well. Special attention is devoted to the case that the points are the points of a triangular lattice.

A compressed (gzip) PostScript file (112 kB) with the full contents of this report can be downloaded by clicking here.

Alternatively, if you like a free hard copy of this report, please send the number of this report, LSE-CDAM-98-05, together with your name and postal address to:
CDAM Research Reports Series
Centre for Discrete and Applicable Mathematics
London School of Economics
Houghton Street
London WC2A 2AE, U.K.
Phone: +44(0)-171-955 7732.
Fax: +44(0)-171-955 6877.
Email: info@maths.lse.ac.uk

Introduction to the CDAM Research Report Series.
CDAM Homepage.

Copyright © London School of Economics & Political Science 2005

Last changed: Wed 9 Feb 2005
For comments go to: http://www.maths.lse.ac.uk/webmaster.html