1 Introduction

The study of conflict-free coloring is motivated by the frequency assignment problem in wireless networks. A wireless network is a heterogeneous network consisting of base stations and agents. The base stations have a fixed location and are interlinked via a fixed backbone network, while the agents are typically mobile and can connect to the base stations via radio links. The base stations are assigned fixed frequencies to enable links to agents. The agents can connect to any base station, provided that the radio link to that particular station has good reception. Good reception is only possible if (i) the base station is located within range, and (ii) no other base station within range of the agent has the same frequency assignment (to avoid interference). Thus the fundamental problem of frequency-assignment in cellular networks is to assign frequencies to base stations so that an agent can always find a base station with unique frequency among the base stations in its range. Naturally, due to cost, flexibility, and other restrictions, one would like to minimize the total number of assigned frequencies.

The study of the above problem was initiated in [9] and continued in a series of recent papers [36, 8, 11, 12, 14, 15]. For a recent survey on the problem and its applications, we refer to [16]. The conflict-free coloring problem can be formally described as follows. Let P⊆ℝ2 be a set of points, and \(\mathcal{R}\) be a set of ranges (e.g., the set of all discs or rectangles in the plane). A conflict-free coloring (CF-coloring in short) of P w.r.t. the range \(\mathcal{R}\) is an assignment of a color to each point pP such that for any range \(T \in \mathcal{R}\) with TP≠0, the set TP contains a point of unique color. Naturally, the goal is to assign a conflict-free coloring to the points of P with the smallest number of colors possible.

The work in [9] presented a general framework for computing a conflict-free coloring for several types of ranges. In particular, for the case where the ranges are discs in the plane, they present a polynomial-time coloring algorithm that uses O(logn) colors for conflict-free coloring, and this bound is shown to be tight. This result was then extended in [12] by considering the case where the ranges are axis-parallel rectangles in the plane. This seems much harder than the disc case, and the work in [12] presented a simple algorithm that uses \(O(\sqrt{n})\) colors. As mentioned in [12], this can be further improved to \(O(\sqrt {n\log\log n/\log n})\) using the sparse neighborhood property of the conflict-free graph, as independently observed by Alon, Krivelevich, and Sudakov [2] and Pach and Tóth [14]. Prior to this paper, this was the best known upper bound for CF-coloring axis-parallel rectangles. A lower bound of Ω(logn) trivially follows from the lower bound for intervals. A related notion is that of the Delaunay graph of a point set P with respect to axis-parallel rectangles, defined as the graph on the vertex set P, whose two points p,qP are connected by an edge if and only if there is an axis-parallel rectangle that contains p and q, but no other points of P. Chen et al. [7] show that there exists a set of n points for which the maximum size of an independent set in the conflict-free graph is O(nlog2logn/logn).

Recent works have shown that one can obtain better upper bounds for special cases of this problem. In [12], it was shown that for the case of random points in a unit square, O(log4 n) colors suffice, and for points lying in an exact uniform \(\sqrt {n} \times\sqrt{n}\) grid, O(logn) colors are sufficient. Chen [5] showed that polylogarithmic number of colors suffice for the case of nearly equal rectangle ranges. Elbassioni and Mustafa [8] asked the following question: Given a set of points P in the plane, can we insert new points Q such that the conflict free coloring of PQ requires fewer colors? They showed that by inserting O(n 1−ϵ) points, PQ can be conflict-free colored using \(\tilde{O}(n^{3(1+\epsilon)/8})\) colors.

While the CF-coloring problem is closed for disc ranges, the upper bounds are very far from the currently known lower bounds for axis-parallel rectangular ranges. It remains very interesting to reduce this gap between upper and lower bounds, and this is, in fact, the main open problem posed in [12]. In this paper, we improve the upper bound significantly.

Theorem 1.1

Any set of n points in2 can be conflict-free colored with respect to rectangle ranges using \(O(n^{\beta^{*}+O(\frac{1}{\sqrt{\log n}})})\) colors, in expected polynomial time, where \(\beta^{*} = \frac{3-\sqrt{5}}{2} < 0.382\).

An immediate corollary of Theorem 1.1 is that the Delaunay graph of any set of points in the plane with respect to axis-parallel rectangles has an independence number Ω(n 0.618).

Our main tool for proving this theorem is a probabilistic coloring technique, introduced in [8], that can be used to get a coloring with weaker properties, which we call quasi-conflict-free coloring. This will be combined with boundary sets, monotone sequences, and careful griding of the point set, in a recursive way, to obtain the claimed result. We start with some definitions and preliminaries in Sect. 2. To illustrate our ideas, we sketch a simple \(\tilde{O}(n^{6/13})\) conflict-free coloring algorithm in Sect. 3. The main algorithm will be given in Sect. 4. We describe the quasi-conflict-free coloring technique in a slightly more general form in Sect. 5. Section 4 contains the analysis of the main algorithm.

2 Preliminaries

By \(\mathcal{R}\subseteq2^{\mathbb{R}^{2}}\), we denote the set of all axis-parallel rectangles. Let P be a set of points in ℝ2.

Definition 2.1

(Conflict-free coloring)

A coloring of P is a function \(\chi:P\mapsto \mathcal{N}\) from P to some finite set \(\mathcal{N}\). A rectangle \(T\in \mathcal{R}\) is said to be conflict-free with respect to a coloring χ if either TP=∅, or there exists a point pPT such that χ(p)≠χ(p′) for all points p′∈PT, distinct from p. A coloring χ is said to be conflict-free (w.r.t. \(\mathcal{R}\)) if every rectangle \(T\in \mathcal{R}\) is conflict-free w.r.t. χ.

In this paper, we shall say that a given procedure is an f(n)-CF-coloring algorithm if it conflict-free colors any set of points of size n with at most f(n) colors. It will be convenient to think of the set of colors \(\mathcal{N}\), which we use to color the points, as a subset of the sequences of natural numbers ℕ=ℕ∪ℕ2∪… This allows us to take unions and products of colors. More precisely, for disjoint subsets P′,P″⊆P and colorings χ′:P′↦ℕ and χ″:P″↦ℕ, we let χ′+χ″ denote the coloring χ:P′∪P″↦ℕ defined by χ(p)=χ′(p) if pP′ and χ(p)=χ″(p) if pP″. For two colorings χ′,χ″:P↦ℕ, we denote by χ′×χ″ the coloring χ:P↦ℕ given by χ(p)=(χ′(p),χ″(p)) for pP.

Definition 2.2

(Boundary sets)

For a point p=(p x,p y)∈ℝ2, define W 1(p)={q∈ℝ2|q xp x,q yp y} to be the upper-right quadrant defined by p. Similarly, let W 2(p),W 3(p), and W 4(p) be the upper-left, lower-right and lower-left quadrants, respectively. Define the boundary set of type i for P, denoted by D i (P), 1≤i≤4, as follows:

$$D_i(P) = \bigl\{p\in P \mid W_i(p)\cap P = \{p\}\bigr\}. $$

Definition 2.3

(Monotonic sets)

Let P={p 1,p 2,…,p k } be a set of points that is sorted by x coordinate. P is (resp. monotonic nonincreasing) if \(p_{j}^{y} \geq p_{i}^{y}\) (resp. \(p_{j}^{y} \leq p_{i}^{y}\)) for all 1≤i<jk.

It is easy to see that the boundary set of type 2 and 3 (resp. type 1 and 4) are monotonic nondecreasing (resp. nonincreasing); see Fig. 1.

Fig. 1
figure 1

Boundary sets: the shaded region represents the lower right quadrant, and the solid black points represent the boundary set D 3(P) of type 3

Definition 2.4

(r-Grid)

Let r∈ℤ>0 be a positive integer. An r-grid on P (see Fig. 2), denoted by G r =G r (P), is an r×r axis-parallel grid containing all points of P. For i=1,…,r, denote by R i and C i the subsets of P lying in the ith row and column of G r , respectively. Denote by B(G r ) the maximum number of points of P in a row or a column of G r . For 1≤h≤2r−1, let \(M^{1}_{h}\) (resp. \(M^{2}_{h}\)) be the set of grid cells lying along a diagonal h of positive slope (resp. negative slope) in G r . For l=2,3 (resp. l=1,4), let \(\mathcal{D}_{l}^{h} = \bigcup_{(i,j)\in M^{1}_{h}} D_{l}(R_{i}\cap C_{j})\) (resp. \(\mathcal{D}_{l}^{h} = \bigcup_{(i,j)\in M^{2}_{h}} D_{l}(R_{i}\cap C_{j})\)) be the union of boundary sets of type l over grid cells in \(M^{1}_{h}\) (resp. \(M^{2}_{h}\)). Let \(\mathcal{D}_{l} = \bigcup_{(i,j)\in G_{r}} D_{l}(R_{i}\cap C_{j})\) be the union of boundary sets of type l over all the grid cells in G r .

Fig. 2
figure 2

r-grid G r : r=4, B(G r )=24, the four types of boundary sets are shown as solid circles in four different colors, and the remaining points are shown as hollow circles. The shaded cells represent the set \(M_{h}^{1}\) for h=3. Note that some points may be in many different boundary sets. In this figure, a point belonging to multiple boundary sets is colored by the color of either one of them (Color figure online)

Note that, for l=2,3 and 1≤h≤2r−1, \(\mathcal{D}_{l}^{h}\) is monotonic nondecreasing, since the grid cells in \(M^{1}_{h}\), which lie along the diagonal of positive slope, are horizontally and vertically separated, and hence the union of D l (R i C j ) (which are monotonic nondecreasing) is also monotonic nondecreasing. By a similar argument, for l=1,4 with \(M^{2}_{h}\) and 1≤h≤2r−1, \(\mathcal{D}_{l}^{h}\) is monotonic nonincreasing.

Definition 2.5

(Quasi-conflict-free coloring)

Given a grid G r on P, we call a coloring \(\chi:P\mapsto \mathcal{N}\) quasi-conflict-free with respect to G r if every axis-parallel rectangle which contains points only from the same row or the same column of G r is conflict-free.

Let G r be an r-grid on a point set P such that B(G r )=B. It is shown in [8] that there exists a quasi-conflict-free coloring of G r requiring \(\tilde{O}(B^{3/4})\) colors.Footnote 1

3 A Simple Conflict-Free Coloring Algorithm Using \(\tilde{O}(n^{6/13})\) Colors

In this section, we sketch a simple algorithm for CF-coloring P in order to illustrate the main ideas. This algorithm CF-colors P using \(\tilde{O}(n^{6/13})\) colors. We deliberately skip some technical details in order to make the main idea as clear as possible. The later sections contain a more detailed analysis.

It will be useful first to illustrate the idea behind the O(n 1/2)-CF-coloring algorithm in [12]. By the Erdős–Szekeres theorem [10], the set of points P, regarded as sequence when ordered by the x-coordinate, has a monotone subsequence of size \(\sqrt{n}\). Clearly, the set I consisting of every other point in this monotone sequence defines an independent set in the conflict-free graph of P. We color all the points in I with one color and then recurse on the rest of the points with a different set of colors. One can easily argue that the resulting coloring will be conflict free since I is an independent set, and that the total number of colors needed is O(n 1/2).

Let \(\mathcal{A}\) be an O(n 1/2) conflict-free coloring algorithm (as the one described above). To reduce the number of colors needed below O(n 1/2), we proceed as follows. Set t=n 7/13. As long as the current point set contains a monotonic sequence of size t, we color alternate points in that sequence with the same color, remove them, and continue with the remaining points using new colors. Since we remove Ω(t) points every time, the number of colors used in this process is O(n 6/13). Let Q be the set of points left after this step, and let m=|Q|. Now, let \(r=m^{\frac{5}{13}}\). Grid Q using G r such that each row and column has \(B=m^{\frac{8}{13}}\) points of P. Compute the boundary sets \(\mathcal{D}_{l}(Q), 1 \leq l \leq4\), and let \(D = \bigcup_{l=1}^{4} D_{l}(Q)\) and Q′=QD. We quasi-CF color Q′ with \(\tilde{O}(B^{3/4})\) colors using the algorithm of [8] (which uses \(\mathcal{A}\) as subroutine). Then, we CF-color D using \(\mathcal{A}\) with a different set of colors.

Lemma 3.1

The above coloring of P is conflict-free.

Proof

Let \(T\in \mathcal{R}\) be a rectangle such that TP≠∅. We show that T contains a point of unique color among the points in TP.

We consider 3 cases:

Case 1. A monotone sequence of size t is found, and we colored every other point in the sequence (set I) with one color: if (TP)∖I≠∅, then by induction and the fact that I and PI are colored with distinct sets of colors, we know that TP contains a point of a unique color. If TPI, then |TP|=1 (since I consists of every other point in a monotone sequence), and the statement trivially holds.

Case 2. TD≠∅: The CF-coloring of D guarantees that there is a point p of unique color among points in TD. Since D and Q′=QD are colored with distinct sets of colors, p is a point of unique color among points in TP also.

Case 3. TD=∅: Let (i,j) be a grid cell of G r defined by the intersection of row R i and column C j . If T contains at least one corner of some grid cell (i,j), TD l (R i C j )≠∅ for some l∈{1,…,4}, contradicting the fact that TD=∅. Therefore, in this case, T lies completely within one row or one column of G r . Since TP≠∅ and TD=∅, we have TQ′≠∅. The quasi-CF coloring of Q′ guarantees that there is a point p of unique color among the points in TQ′. p is also a point of unique color among points in TP. □

We now bound the total number of colors used by our algorithm. As argued before, the number of colors used in the first step (removing monotonic sequences of size t) is Ω(n 6/13). Quasi-CF-coloring of Q requires \(\tilde{O}(n^{{\frac{8}{13}} \times\frac {3}{4}}) = \tilde{O}(n^{6/13})\) colors. To bound the number of colors used in CF-coloring D, we first bound the size of D: \(\vert \mathcal{D}_{l}^{h} \vert\leq t\) for all h and l, because each \(\mathcal{D}_{l}^{h}\) is a monotonic sequence. Since \(D = \bigcup_{l,h} \mathcal{D}_{l}^{h}\) over 1≤h≤2m 5/13−1, and 1≤l≤4, we have |D|=O(n 12/13). Thus, the CF-coloring of D (using the O(n 1/2)-coloring algorithm \(\mathcal{A}\)) requires O(n 6/13) colors. The total number of colors used by our algorithm is thus \(\tilde{O}(n^{6/13})\).

4 Improved Conflict Free Coloring

In the algorithm described in Sect. 3, we used an O(n 1/2)-“black-box” \(\mathcal{A}\) for CF-coloring the boundary set D and the quasi-CF-coloring of P′. As a result, we obtained an \(\tilde{O}(n^{6/13})\) CF-coloring algorithm. We can improve this coloring further by using this \(\tilde{O}(n^{6/13})\) as a new black-box for CF-coloring the boundary set D and quasi-CF-coloring of P′. An easy calculation shows that the number of colors used is asymptotically smaller than \(\tilde{O}(n^{6/13})\).

This bootstrapping approach can be taken to the limit. This results in a sequence of strictly improved algorithms, \(\mathcal{A}=\mathcal{A}_{0},\mathcal{A}_{1},\mathcal{A}_{2},\ldots{}\). For k=1,2,…, the structure of \(\mathcal{A}_{k}\) is similar to the algorithm described in Sect. 3: Grid the point set P using G r , where \(r=n^{1-\alpha_{k}}\) for some α k ; Partition P into boundary set D and P′=PD and use algorithm \(\mathcal{A}_{k-1}\) for CF-coloring D and quasi-CF-coloring P′. We choose the parameter α k such that both the CF-coloring of D and quasi-CF-coloring of P′ balance-out into using \(\tilde{O}(n^{\beta_{k}})\) colors for some β k as small as possible.

Ideally, one would like to always recursively apply algorithm \(\mathcal{A}_{\infty}\) to get a bound of \(\tilde{O}(n^{\beta_{\infty}})\) on the number of colors (assuming that these limits exist). However, there is a technical problem with such a recursion: the sublinearity of the bound on the number of colors implies that the power of the logarithmic factor increases exponentiallyFootnote 2 with k. To solve this problem, we can stop the recursion at a level of \(O(\log\frac{1}{\epsilon})\), settling at a bound of \(\tilde{O}(n^{\beta_{\infty}+\epsilon})\) for any arbitrarily small constant ϵ>0. Analyzing this approachFootnote 3 is however technically complicated, and we present an alternate method here, which is asymptotically better in terms of the number of colors, but with possibly worse constants.

In the rest of the paper, logarithms are with base 2. Let \(\beta^{*} = (3-\sqrt{5})/2\), α =1−β , c=219, and \(n_{0} = 2^{(14c)^{2}}\). Define the functions \(\alpha(n) = \alpha^{*} - 5c/\sqrt{\log{n}}\), \(\beta(n) = \beta^{*} + 9c/\sqrt{\log{n}}\), and \(\gamma(n)= \alpha^{*} - 7c/\sqrt{\log{n}}\).

Let P be a set of n points. If nn 0, we use any CF-coloring algorithm to color P. Otherwise, we use the same approach as in Sect. 3. Namely, if P contains a monotonic chain of points of size m=2n γ(n), then we color alternate points of the chain with one color and recursively color the rest of the points in P using a new set of colors. Otherwise (the size of any monotonic chain in P is at most m), we construct a grid G so that each row and column of G contains at most n α(n) points. Let D be the set of all points belonging to the boundary sets of the cells of G. We conflict free-color D recursively using our CF-coloring procedure, and quasi-CF-color the rest of the points using a different set of colors. In the quasi conflict-free coloring algorithm, we use a recursive call to the conflict-free coloring procedure. (However, since we are calling the quasi conflict-free coloring algorithm only for smaller-size point sets, there is no circularity here.) The coloring procedure is given as Algorithm 1.

Algorithm 1
figure 3

Procedure \(\mathcal{A}(P,S)\)

The structure of the above algorithm is the same as the algorithm described in Sect. 3. Hence, by Lemma 3.1 the coloring returned by the algorithm is conflict-free.

In the next section, we bound the number of colors needed by the quasi-CF-coloring algorithm. We use this result in Sect. 6 to analyze the number of colors needed by Algorithm 1.

5 Generalized Quasi-conflict Free Coloring

Given an r-grid G r on point set P, we start by coloring the points of each column, using a CF-coloring algorithm \(\mathcal{A}\) as a black-box. We use the same set of colors for all columns. Then randomly and independently for each column, we redistribute the colors on the different color classes of the column. Finally, a recoloring step is applied on each monochromatic set of points in each row, again using algorithm \(\mathcal{A}\) as the CF-coloring procedure. The color assigned to a point is the concatenation of its first and second colorings. A formal description of this procedure is given as Algorithm 2.

Algorithm 2
figure 4

Procedure QCFC\((P,\mathcal{A},G_{r},S)\)

The following is a straightforward generalization of Theorem 3 in [8], in which \(\mathcal{A}\) is used as the CF-procedure (instead of the \(\sqrt{n}\)-procedure used in [8]).

Theorem 5.1

Given any point set P⊆ℝ2, a grid G r with B=B(G r ) on P, and an f(⋅)-conflict-free coloring algorithm \(\mathcal{A}\) such that B≥4 and

$$ r\cdot f(B) (\log B)^{(-\log B)/8}\leq\frac{1}{2}, $$
(1)

procedure QCFC returns a quasi-conflict-free coloring of G r using

$$ q(B)=f(B)f \biggl(\frac{B \log B }{f(B)} \biggr) $$
(2)

colors, in expected polynomial time.

6 Analysis

We now show an improved bound on the number of colors required for conflict free coloring a set of n points. Namely, we show that any set of points n can always be conflict-free colored with f(n):=n β(n) colors. The function f(n) is clearly monotonically increasing and is chosen so that it satisfies the following.

Claim 6.1

For n>n 0, f(n),α(n), and γ(n) satisfy the following inequalities:Footnote 4

(3)
(4)
(5)

We defer the proof of the above inequalities and first show the following.

Theorem 6.1

Any set of n points can be conflict-free colored using f(n) colors.

Proof

We show that Algorithm 1 requires f(n) colors to CF-color any point set P of size n. The proof is by induction on n. The theorem is trivially true for nn 0 since for such n, β(n)>1, and therefore f(n)>n. Let P be a set of n>n 0 points and assume that for point sets of smaller size, the statement is true. If P contains a monotonic chain of points of size u=2n γ(n), then the algorithm colors alternate points of the chain with one color and recursively colors the rest of the points in P using a new set of colors. Thus we have colored the point set using 1+f(nn γ(n)) colors which by the first inequality in Claim 6.1 is at most f(n). On the other hand, if the size of any monotonic chain in P is at most u, then we construct a grid G so that each row and column of G contains at most n α(n) points. There are n 1−α(n) rows and columns in G. Let D be the set of all points belonging to the boundary sets of the cells of G. Since D can be partitioned into at most 8⋅n 1−α(n) monotonic sets, we have |D|≤u⋅8⋅n 1−α(n)≤16⋅n 1−α(n)+γ(n). We conflict-free color D using f(16⋅n 1−α(n)+γ(n)) colors and quasi-conflict-free color the rest of the points using a different set of colors. For this, we invoke the algorithm described in Sect. 5 with the grid G. Since by (5), condition (1) is satisfied, we are guaranteed by Theorem 5.1 to use at most \(f(n^{\alpha (n)})\cdot f(\frac{n^{\alpha(n)} \log{n^{\alpha(n)}}}{f(n^{\alpha (n)})})\) colors for the quasi-conflict-free coloring step. By the second inequality in Claim 6.1 the total number of colors used is at most f(n). □

Proof of Claim 6.1

For brevity of notation, we denote, respectively, α(n), β(n), and γ(n) by α, β, and γ, whenever convenient. Let us start with the first inequality:

The first inequality follows by rearranging the terms. We prove the second inequality in two parts. We show that the quantities f(16⋅n 1−α+γ) and \(f(n^{\alpha })\cdot f(\frac{n^{\alpha} \log{n^{\alpha}}}{f(n^{\alpha})})\) are both at most f(n)/2. It follows that their sum is at most f(n). We first observe some simpler inequalities that we need. For any λ>0,

$$ f\bigl(n^\lambda\bigr) = \bigl(n^{\lambda} \bigr)^{\beta^* + 9c/\sqrt{\log{n^\lambda }}} = n^{\lambda\beta^* + 9c\sqrt{\lambda}/\sqrt{\log{n}}}. $$
(6)

Using the above with λ=α, we have

$$ f\bigl(n^\alpha\bigr) = n^{\alpha\beta^* + 9c\sqrt{\alpha}/\sqrt{\log{n}}} = n^{\alpha^* \beta^* + (9c\sqrt{\alpha} - 5c\beta^*)/\sqrt{\log{n}}}. $$
(7)

It follows from the above that

(8)
(9)

From the above we get

(10)

Therefore,

(11)

Using (8) and (11), we have

(12)

On the other hand,

(13)

From (12) and (13) we conclude the second inequality in the claim.

Finally, it remains to verify the third inequality:

The claim follows. □