1 January 2003 in SIAM Journal on Computing
Motivated by a frequency assignment problem in cellular networks, we introduce and study a new coloring problem that we call minimum conflict-free coloring (min-CF-coloring). In its general form, the input of the min-CF-coloring problem is a set system $(X,{\cal S})$, where each $S \in {\cal S}$ is a subset of X. The output is a coloring $\chi$ of the sets in ${\cal S}$ that satisfies the following constraint: for every $x \in X$ there exists a color i and a unique set $S \in {\cal S}$ such that $x \in S$ and $\chi(S) = i$. The goal is to minimize the number of colors used by the coloring $\chi$. Min-CF-coloring of general set systems is not easier than the classic graph coloring problem. However, in view of our motivation, we consider set systems induced by simple geometric regions in the plane. In particular, we study disks (both congruent and noncongruent), axis-parallel rectangles (with a constant ratio between the smallest and largest rectangle), regular hexagons (with a constant ratio between the smallest and largest hexagon), and general congruent centrally symmetric convex regions in the plane. In all cases we have coloring algorithms that use O(log n) colors (where n is the number of regions). Tightness is demonstrated by showing that even in the case of unit disks, $\Theta(\log n)$ colors may be necessary. For rectangles and hexagons we also obtain a constant-ratio approximation algorithm when the ratio between the largest and smallest rectangle (hexagon) is a constant. We also consider a dual problem of CF-coloring points with respect to sets. Given a set system $(X,{\cal S})$, the goal in the dual problem is to color the elements in X with a minimum number of colors so that every set $S \in {\cal S}$ contains a point whose color appears only once in S. We show that O(log |X|) colors suffice for set systems in which X is a set of points in the plane and the sets are intersections of X with scaled translations of a convex region. This result is used in proving that O(log n) colors suffice in the primal version.
1 March 2004 in Journal of the ACM
A collection of simple closed Jordan curves in the plane is called a family of pseudo-circles if any two of its members intersect at most twice. A closed curve composed of two subarcs of distinct pseudo-circles is said to be an empty lens if the closed Jordan region that it bounds does not intersect any other member of the family. We establish a linear upper bound on the number of empty lenses in an arrangement of n pseudo-circles with the property that any two curves intersect precisely twice. We use this bound to show that any collection of n x -monotone pseudo-circles can be cut into O ( n 8/5 ) arcs so that any two intersect at most once; this improves a previous bound of O ( n 5/3 ) due to Tamaki and Tokuyama. If, in addition, the given collection admits an algebraic representation by three real parameters that satisfies some simple conditions, then the number of cuts can be further reduced to O ( n 3/2 (log n ) O (α(
s
( n )) ), where α( n ) is the inverse Ackermann function, and s is a constant that depends on the the representation of the pseudo-circles. For arbitrary collections of pseudo-circles, any two of which intersect exactly twice, the number of necessary cuts reduces still further to O ( n 4/3 ). As applications, we obtain improved bounds for the number of incidences, the complexity of a single level, and the complexity of many faces in arrangements of circles, of pairwise intersecting pseudo-circles, of arbitrary x -monotone pseudo-circles, of parabolas, and of homothetic copies of any fixed simply shaped convex curve. We also obtain a variant of the Gallai--Sylvester theorem for arrangements of pairwise intersecting pseudo-circles, and a new lower bound on the number of distinct distances under any well-behaved norm.
7 April 2005 in Discrete & Computational Geometry
We study conflict-free colorings, where the underlying set systems arise in geometry. Our main result is a general framework for conflict-free coloring of regions with low union complexity. A coloring of regions is conflict-free if for any covered point in the plane, there exists a region that covers it with a unique color (i.e., no other region covering this point has the same color). For example, we show that we can conflict-free color any family of n pseudo-discs with O(log n) colors.
1 January 2007 in SIAM Journal on Discrete Mathematics
A finite family $\mathcal{R}$ of simple Jordan regions in the plane defines a hypergraph $H=H(\mathcal{R})$ where the vertex set of H is $\mathcal{R}$ and the hyperedges are all subsets $S \subset \R$ for which there is a point p such that $S = \{r \in \mathcal{R} | p \in r\}$. The chromatic number of $H(\mathcal{R})$ is the minimum number of colors needed to color the members of $\mathcal{R}$ such that no hyperedge is monochromatic. In this paper we initiate the study of the chromatic number of such hypergraphs and obtain the following results: (i) Any hypergraph that is induced by a family of n simple Jordan regions such that the maximum union complexity of any k of them (for $1\leq k \leq m$) is bounded by $\mathcal{U}(m)$ and $\frac{\mathcal{U}(m)}{m}$ is a nondecreasing function is $O(\frac{\mathcal{U}(n)}{n})$-colorable. Thus, for example, we prove that any finite family of pseudo-discs can be colored with a constant number of colors. (ii) Any hypergraph induced by a finite family of planar discs is four colorable. This bound is tight. In fact, we prove that this statement is equivalent to the four-color theorem. (iii) Any hypergraph induced by n axis-parallel rectangles is $O(\log n)$-colorable. This bound is asymptotically tight. Our proofs are constructive. Namely, we provide deterministic polynomial-time algorithms for coloring such hypergraphs with only “few” colors (that is, the number of colors used by these algorithms is upper bounded by the same bounds we obtain on the chromatic number of the given hypergraphs). As an application of (i) and (ii) we obtain simple constructive proofs for the following: (iv) Any set of n Jordan regions with near linear union complexity admits a conflict-free (CF) coloring with polylogarithmic number of colors. (v) Any set of n axis-parallel rectangles admits a CF-coloring with $O(\log^2(n))$ colors.
1 January 2007 in SIAM Journal on Computing
We consider an online version of the conflict‐free coloring of a set of points on the line, where each newly inserted point must be assigned a color upon insertion, and at all times the coloring has to be conflict‐free, in the sense that in every interval I there is a color that appears exactly once in I. We present deterministic and randomized algorithms for achieving this goal, and analyze their performance, that is, the maximum number of colors that they need to use, as a function of the number n of inserted points. We first show that a natural and simple (deterministic) approach may perform rather poorly, requiring $\Omega(\sqrt{n})$ colors in the worst case. We then derive two efficient variants of this simple algorithm. The first is deterministic and uses $O(\log^2 n)$ colors, and the second is randomized and uses $O(\log n)$ colors with high probability. We also show that the $O(\log^2 n)$ bound on the number of colors used by our deterministic algorithm is tight on the worst case. We also analyze the performance of the simplest proposed algorithm when the points are inserted in a random order and present an incomplete analysis that indicates that, with high probability, it uses only $O(\log n)$ colors. Finally, we show that in the extension of this problem to two dimensions, where the relevant ranges are disks, n colors may be required in the worst case.
1 August 2009 in Computational Geometry