On the chromatic number of some geometric hypergraphs
On the chromatic number of some geometric hypergraphs
复制标题
DOI：
10.1145/1109557.1109593
复制
发表时间：
2006-01
期刊：
影响因子：
--
通讯作者：
Shakhar Smorodinsky
中科院分区：
文献类型：
--
作者：
Shakhar Smorodinsky
平面上简单Jordan区域的有限族R定义了一个超图H = H(R)，其中H的顶点集是R，超边都是S∧R，其中存在一个点p使得S = {R∈R|p∈R， H(R)的色数是为R的元素上色所需的最小色数，使得没有超边是单色的。本文研究了这类超图的色数。我们得到了以下结果：(i)由n个简单约当区域（不一定是凸的）族所导出的任何超图，其中任意m个简单约当区域的并并复杂度由u(m)给出且u(m)/m是非递减的，则该超图是O（u(n)/n）可着色的。因此，举例来说，我们证明了任何有限族的假盘都可以用常数种颜色着色。（ii）由有限平面圆盘族诱导的任何超图都是四色的。这个界限很紧。事实上，我们证明了这个命题等价于四色定理。（iii）由n个轴平行矩形诱导的任何超图都是O（log n）可着色的。这个界是渐近紧的。我们的证明是建设性的。即我们提供确定性多项式时间算法等着色超图只有“几”颜色(也就是说,这些算法所使用的颜色的数量是由同一范围的上界得到给定超图的色数)的应用程序(i)和(ii)我们获得简单的建设性的依据如下:(iv)任何一组n约旦地区附近线性联盟承认复杂性无冲突(CF)和polylogarithmic数量的颜色着色。(v)任何n个轴平行矩形的集合都允许用O（log2(n)）种颜色的cf着色。
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(log2(n)) colors.