TY - JOUR
T1 - Conflict-free colorings of shallow discs
AU - Alon, Noga
AU - Smorodinsky, Shakhar
N1 - Funding Information:
∗Research supported in part by the Israel Science Foundation, by the Hermann Minkowski Minerva center for Geometry at Tel Aviv University, by NSF grant CCR-0324906, by the James Wolfensohn fund and by the State of New Jersey. †Research supported by the NSF Mathematical Sciences Postdoctoral Fellowship award 0402492.
PY - 2008/12
Y1 - 2008/12
N2 - We prove that any collection of n discs in which each one intersects at most k others, can be colored with at most O(log3 k) colors so that for each point p in the union of all discs there is at least one disc in the collection containing p whose color differs from that of all other members of the collection that contain p. This is motivated by a problem on frequency assignment in cellular networks, and improves the best previously known upper bound of O(log n) when k is much smaller than n.
AB - We prove that any collection of n discs in which each one intersects at most k others, can be colored with at most O(log3 k) colors so that for each point p in the union of all discs there is at least one disc in the collection containing p whose color differs from that of all other members of the collection that contain p. This is motivated by a problem on frequency assignment in cellular networks, and improves the best previously known upper bound of O(log n) when k is much smaller than n.
KW - Combinatorial geometry
KW - Conflict-free colorings
KW - Wireless networks
UR - http://www.scopus.com/inward/record.url?scp=58149235017&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=58149235017&partnerID=8YFLogxK
U2 - 10.1142/S0218195908002775
DO - 10.1142/S0218195908002775
M3 - Article
AN - SCOPUS:58149235017
SN - 0218-1959
VL - 18
SP - 599
EP - 604
JO - International Journal of Computational Geometry and Applications
JF - International Journal of Computational Geometry and Applications
IS - 6
ER -