Centre for Discrete and Applicable Mathematics
	CDAM Research Report, LSE-CDAM-98-05 March 1998

Abstract

Given a set  V  of points in the plane, a sequence  d₀,d₁, . . . ,d_k  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  x, y in V  are two points with euclidean distance less than  d_i,  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  d₀  is given, good labellings can be obtained by using so-called strict tilings. We extend these results to the case that higher level constraints  d₀,d₁, . . . ,d_k  occur. In particular we study conditions that guarantee that a strict tiling, satisfying only the one constraint  d₀,  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.

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