On the chromatic number of some geometric hypergraphs

ABSTRACT

A finite family R of simple Jordan regions in the plane defines a hypergraph H = H(R) where the vertex set of H is R and the hyperedges are all subsets S ⊂ R for which there is a point p such that S = {r ∈ R|p ∈ r. The chromatic number of H(R) is the minimum number of colors needed to color the members of R such that no hyperedge is monochromatic. In this paper we initiate the study of the chromatic number of such hypergraphs. We obtain the following results:(i) any hypergraph that is induced by a family of n simple Jordan regions (not necessarily convex) such that the union complexity of any m of them is given by u(m) and u(m)/m is non-decreasing is O(u(n)/n)-colorable. Thus, for example we prove that any finite family of pseudodiscs 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²(n)) colors.

REFERENCES

• 1: N. Alon and S. Smorodinsky. Conflict-free colorings of shallow discs, manuscript, 2005.
• 2: K. Appel and W. Haken, "Every planar map is 4-colorable - 1: Discharging", Illinois Journal of Mathematics, 21:421--490, 1977.
• 3: K. Appel and W. Haken, "Every planar map is 4-colorable - 2: Reducibility", Illinois Journal of Mathematics, 21:491--567, 1977.
• 4: K. L. Clarkson , P. W. Shor, Applications of random sampling in computational geometry, II, Discrete & Computational Geometry, v.4 n.5, p.387-421, 1989 [doi>10.1007/BF02187740]
• 5: Micha Sharir , Pankaj K. Agarwal, Davenport-Schinzel sequences and their geometric applications, Cambridge University Press, New York, NY, 1996
• 6: Guy Even , Zvi Lotker , Dana Ron , Shakhar Smorodinsky, Conflict-Free Colorings of Simple Geometric Regions with Applications to Frequency Assignment in Cellular Networks, SIAM Journal on Computing, v.33 n.1, p.94-136, 2004 [doi>10.1137/S0097539702431840]
• 7: Amos Fiat , Meital Levy , Jiří Matoušek , Elchanan Mossel , János Pach , Micha Sharir , Shakhar Smorodinsky , Uli Wagner , Emo Welzl, Online conflict-free coloring for intervals, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 8: Sariel Har-Peled , Shakhar Smorodinsky, Conflict-Free Coloring of Points and Simple Regions in the Plane, Discrete & Computational Geometry, v.34 n.1, p.47-70, July 2005 [doi>10.1007/s00454-005-1162-6]
• 9: H. Kaplan and M. Sharir, Online CF coloring for halfplanes, congruent disks, and axis-parallel rectangles, manuscript, 2004.
• 10: Klara Kedem , Ron Livne , János Pach , Micha Sharir, On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles, Discrete & Computational Geometry, v.1 n.1, p.59-71, 1986 [doi>10.1007/BF02187683]
• 11: P. Koebe, Kontaktprobleme der konformen Abbildung, Ber. Sächs. Akad. Wiss. Leipzig, Math-Phys. KL. 88 141--164, 1936.
• 12: J. Pach and G. Tóth. Conflict free colorings. In Discrete and Computational Geometry, The Goodman-Pollack Festschrift. Springer Verlag, Heidelberg, 2003.
• 13: J. Pach and G. Tardos. Personal communication.
• 14: S. Smorodinsky, Combinatorial Problems in Computational Geometry, Ph.D Dissertation, School of Computer Science, Tel-Aviv University, 2003.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Hypergraphs

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Number-theoretic computations (e.g., factoring, primality testing)
      F.2.2 Nonnumerical Algorithms and Problems

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms, Theory