Consider a cellular network consisting of a set of base stations, where the signal from a given base station can be received by clients within a certain distance from the base station. In general, these regions will overlap. For a client, this may lead to interference of the signals. Thus one would like to assign frequen- cies to the base stations such that for any client within reach of at least one base station, there is a base station within reach with a unique frequency (among all the ones within reach). The goal is to do this using only few distinct frequencies. Recently, Even et al.  introduced conict-free colorings, as de ned next, to model this problem. Let S be a set of n objects, and let R be a, possibly in nite, family of ranges. In this paper, we only consider objects and ranges that are subsets of R2, or sometimes of R1. For a range r 2 R, let S(r) be the subset of objects from S intersecting the range r. A conict-free coloring (CF-coloring) of S with respect to R is a coloring of S with the following property : for any range r 2 R for which S(r) 6= ; there is an object o 2 S(r) with a unique color in S(r), that is, with a color not used by any other object in S(r). Trivially, a conict-free coloring always exists: just assign a different color to each object. However, one would like to nd a coloring with only few colors. This is the conict-free coloring problem. Note that if we take S to be a set of disks|namely, the regions within reach of each base station|and we take R to be the set of all points in R2, then we get exactly the range-assignment problem discussed earlier. However, other versions|for example the dual version, where S is a point set and R is the family of all disks --- are interesting as well.
20th Canadian Conference in Computational Geometry: Cccg 2008, 2008, p. 95-98
Main Research Area:
Canadian Conference on Computational Geometry, 2008