We study the following geometric hypergraph coloring problem: given a planar point set and an integer k, we wish to color the points with k colors so that any axis-aligned strip containing sufficiently many points contains all colors. We show that if the strip contains at least 2k − 1 points, such a coloring can always be found. In dimension d, we show that the same holds provided the strip contains at least k(4 ln k + ln d) points. We also consider the dual problem of coloring a given set of axis-aligned strips so that any sufficiently covered point in the plane is covered by k colors. We show that in dimension d the required coverage is at most d(k − 1) + 1. This complements recent impossibility results on decomposition of strip coverings with arbitrary orientations. From the computational point of view, we show that deciding whether a three-dimensional point set can be 2-colored so that any strip containing at least three points contains both colors is NP-complete. This shows a big contrast with the planar case, for which this decision problem is easy.
展开▼
机译：我们研究以下几何超图着色问题：给定一个平面点集和一个整数k，我们希望使用k种颜色对这些点进行着色，以便包含足够多点的任何与轴对齐的条带都包含所有颜色。我们显示出，如果条带至少包含2k-1个点，则总是可以找到这种颜色。在维d中，我们表明只要带包含至少k（4 ln k + ln d）个点，则保持不变。我们还考虑了给一组给定的轴向对齐的条带着色的双重问题，以便平面中任何足够覆盖的点都可以被k种颜色覆盖。我们表明，在维d中，所需的覆盖率最多为d（k − 1）+1。这补充了最近对带任意方向的带状覆盖物分解的不可能性结果。从计算的角度来看，我们表明确定三维点集是否可以是2色的，以便任何包含至少三个点的带都包含两种颜色是NP完全的。这与平面情况形成了很大的对比，对于这种情况，此决策问题很容易解决。
展开▼
