Geometric Coverage Of Conflict-free Coloring Problem

The minimum conflict free coloring problem was introduced by Even et.[16] as to solve the frequency allocation problem that arises in wireless communication. In this model, servers (base stations) and clients (mobile) are connected by radio links. The client automatically scans frequencies in search of a server with a good reception. To avoid interference between base stations, the client needs to choose a specific frequency such that only one of the reachable base stations is assigned with that frequency. And because the spectrum is limited and costly, the goal is to minimize the total number of frequencies assigned to the base stations.In the scenario of wireless communication, the clients are modeled as points and the subsets of clients are covered by a base station are modeled as ranges. A dual problem considers to treat base stations as points and clients as some geometric regions. The ranges are subsets of base stations covered by these regions. Formally, the above problem is defined on a range space and is referred to as minimum conflict free (CF) coloring problem.A conflict-free coloring for unit discs is a coloring on the discs such that for every point p on the plane there is a disc among the discs covering p has a color different from that of the rest of the discs that covers p. In the dynamic offline setting, a sequence of unit discs arrive one-by-one and we need to color them in that order and maintain the conflict-free property for the discs arrived so far. In this paper, we give an algorithm that colors a sequence of n unit discs in this setting using O(logn) colors.