0
$\begingroup$

Is it possible to find an optimization to the following theoretical case?

Given is a cellular (phone) system with hexagonal cells, where the volume of transmission and the size of the cells are designed such that the same band (frequency) can be used by two cells that don't share a common edge. It can be assumed that the collection range of bands (frequencies) can be divided into $n$ equal groups of band (frequencies) ranges in order to maximize the number of cellular calls that can be made in parallel in a given cell.

How can we find $n$?

I thought about the clustering of frequencies, i.e, a function $\{f_1,...,f_n\}$, and then, using the given topology (hexagonal), construct the clustering using the intuition that a cluster of size $n$ can be constructed if and only if $n=i^2+j^2+ij$. However, I think I am going in the wrong direction since I am not sure how to handle that the "same band (frequency) can be used by two cells that don't share a common edge". Here I am lost.

Is there an efficient solution to that?

A relevant picture:

enter image description here

Improve this question
$\endgroup$
3
  • $\begingroup$ Welcome to Computer Science! I have made some edits to your post to improve clarity. In particular, refrain from adding "EDIT: [...]" sections separate from your post's main content; your question should be clear to understand for the majority of the audience, that is, people who are reading the question for the first time. $\endgroup$
    – dkaeae
    Mar 14, 2019 at 16:59
  • $\begingroup$ You're looking for the chromatic number of the hexagonal grid (or more accurately its dual, the triangular grid), which is 7. Your image shows a coloring with 7 colors. See also en.wikipedia.org/wiki/Hadwiger%E2%80%93Nelson_problem. $\endgroup$
    – Yuval Filmus
    Mar 14, 2019 at 17:13
  • $\begingroup$ could you please elaborate on the way you obtained the result 7? it is very important to me to understand the why behind the answer so i could apply it to similar problems if needed $\endgroup$
    – npl01
    Mar 14, 2019 at 17:47

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.