Weak conflict-free colorings of point sets and simple regions
Balázs Keszegh · 2007
In this paper we consider the weak conflict-free colorings of regions and points. This is a natural relaxation of conflict-free coloring [ELRS03]. One of the most interesting type of regions to consider for this problem is that of the axis-parallel rectangles. We completely solve the problem for a special case of them, for bottomless rectangles. We also give complete answer for half-planes and pose several open problems. Moreover we give efficient algorithms for coloring with the needed number of colors. For space limitations we do not give the proofs in this version of the paper, to represent the proof techniques we give one proof in the Appendix. 1 Preliminaries Motivated by a frequency assignment problem in cellular telephone networks, Even, Lotker, Ron and Smorodinsky [ELRS03] studied the following problem. Cellular networks facilitate communication between fixed base stations and moving clients. Fixed frequencies are assigned to base-stations to enable links to clients. Each client continuously scans frequencies in search of a base-station within its range with good reception. The fundamental problem of frequency assignment in cellular networks is to assign frequencies to base-stations such that every client is served by some base-station, i.e. it lies within the range of the station and no other station within its reception range has the same frequency. Given a fixed set of base-stations we want to minimize the number of assigned frequencies. First we assume that the ranges are determined by the clients, i.e. if a base-station is in the range of some client, then they can communicate. Let P be the set of base-stations and F the set of all possible ranges of any client. Given some set F of planar regions and a finite set of points P we define cf(F, P ) as the smallest number of colors which are enough to color the points of P such that in every region of F containing at least one point, there is a point whose color is unique among the points in that region. The maximum over all point sets of size n is the so called conflict-free coloring number (cf-coloring in short), denoted by cf(F, n).