Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

There are arbitrarily large finite sets of points in $\mathbb R^3$ whose Voronoi-domains intersect all pairwise in $2-$dimensional polytopes. This shows that one needs infinitely many colours in order to colour "maps" of convex countries in $\mathbb R^d$ for $d\geq 3$.

The situation is however much better if the countries (in infinite number) are the Voronoi-cells of a $d-$dimensional lattice $\Lambda$. They can always be coloured with $2^d$ colours according to the reduction modulo $2\Lambda$ of their lattice point.

This is however not optimal as shown already by the $2-$dimensional lattices which can always be 3-coloured (in the generic case not corresponding to lattices with orthogonal bases).

How far is the upper bound $2^d$ from the smallest upper bound? (I ignore the answer even for $\mathbb R^3$.)

share|improve this question
Related: mathoverflow.net/questions/11453 –  Steve Huntsman May 8 '13 at 19:30
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.