Conflict-free coloring of points and simple regions in the plane

被引:62
作者
Har-Peled, S
Smorodinsky, S
机构
[1] Univ Illinois, Dept Comp Sci, Urbana, IL 61801 USA
[2] Swiss Fed Inst Technol, Inst Theoret Informat, IFW, CH-8092 Zurich, Switzerland
基金
美国国家科学基金会;
关键词
D O I
10.1007/s00454-005-1162-6
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
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.
引用
收藏
页码:47 / 70
页数:24
相关论文
共 19 条
[1]   Coloring graphs with sparse neighborhoods [J].
Alon, N ;
Krivelevich, M ;
Sudakov, B .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 1999, 77 (01) :73-82
[2]  
Alon N., 2000, PROBABILISTIC METHOD
[3]  
[Anonymous], 1999, GEOMETRIC DISCREPANC
[4]  
[Anonymous], 2000, Geometry, Spinors and Applications
[5]  
Chazelle B., 2000, DISCREPANCY METHOD
[6]   APPLICATIONS OF RANDOM SAMPLING IN COMPUTATIONAL GEOMETRY .2. [J].
CLARKSON, KL ;
SHOR, PW .
DISCRETE & COMPUTATIONAL GEOMETRY, 1989, 4 (05) :387-421
[7]  
Efrat A., 1999, Proceedings of the Fifteenth Annual Symposium on Computational Geometry, P134, DOI 10.1145/304893.304958
[8]   On the complexity of the union of fat convex objects in the plane [J].
Efrat, A ;
Sharir, M .
DISCRETE & COMPUTATIONAL GEOMETRY, 2000, 23 (02) :171-189
[9]   Nice point sets can have nasty delaunay triangulations [J].
Erickson, J .
DISCRETE & COMPUTATIONAL GEOMETRY, 2003, 30 (01) :109-132
[10]   Conflict-free colorings of simple geometric regions with applications to frequency assignment in cellular networks [J].
Even, G ;
Lotker, Z ;
Ron, D ;
Smorodinsky, S .
SIAM JOURNAL ON COMPUTING, 2003, 33 (01) :94-136