Conflict-free colorings of shallow discs

Noga Alon, Shakhar Smorodinsky

Research output: Contribution to journalArticle

6 Scopus citations

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(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.

Original languageEnglish (US)
Pages (from-to)599-604
Number of pages6
JournalInternational Journal of Computational Geometry and Applications
Volume18
Issue number6
DOIs
StatePublished - Dec 1 2008
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Geometry and Topology
  • Computational Theory and Mathematics
  • Computational Mathematics
  • Applied Mathematics

Keywords

  • Combinatorial geometry
  • Conflict-free colorings
  • Wireless networks

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

  • Cite this