MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
Related: – Steve Huntsman May 8 '13 at 19:30

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.