### Abstract

We prove that any collection of n discs in which each one intersects at most k others, can be colored with at most O(log^{3} 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 assignments in cellular networks, and improves the best previously known upper bound of O(log n) when k is much smaller than n.

Original language | English (US) |
---|---|

Title of host publication | Proceedings of the Twenty-Second Annual Symposium on Computational Geometry 2006, SCG'06 |

Publisher | Association for Computing Machinery (ACM) |

Pages | 41-43 |

Number of pages | 3 |

ISBN (Print) | 1595933409, 9781595933409 |

DOIs | |

State | Published - Jan 1 2006 |

Externally published | Yes |

Event | 22nd Annual Symposium on Computational Geometry 2006, SCG'06 - Sedona, AZ, United States Duration: Jun 5 2006 → Jun 7 2006 |

### Publication series

Name | Proceedings of the Annual Symposium on Computational Geometry |
---|---|

Volume | 2006 |

### Other

Other | 22nd Annual Symposium on Computational Geometry 2006, SCG'06 |
---|---|

Country | United States |

City | Sedona, AZ |

Period | 6/5/06 → 6/7/06 |

### All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Geometry and Topology
- Computational Mathematics

### Keywords

- Conflict-free coloring
- Frequency-assignment
- Wireless

## Fingerprint Dive into the research topics of 'Conflict-free colorings of shallow discs'. Together they form a unique fingerprint.

## Cite this

Alon, N., & Smorodinsky, S. (2006). Conflict-free colorings of shallow discs. In

*Proceedings of the Twenty-Second Annual Symposium on Computational Geometry 2006, SCG'06*(pp. 41-43). (Proceedings of the Annual Symposium on Computational Geometry; Vol. 2006). Association for Computing Machinery (ACM). https://doi.org/10.1145/1137856.1137864