I just built my own OpenGL Voronoi diagram calculator.
After having looked at a few randomly generated images, I grew curious if it is possible to prove or disprove that some particular choice of metric will give more frequently occuring $\epsilon$ neighborhoods where $4$ different areas are present.
In other words, given $N$ points $p_k$ uniformly placed on $[0,1]^2$ splitting the plane into different areas so that each point $p$ is assigned color $c_k$ for $k$ for which $\min_k \|p-p_k\|$, how can I find the expected number of $\epsilon$ neighborhoods which have 4 different $k$ within it.
How will this number be different for different choices of metrics and of $N$?
With $\epsilon$-neighborhood around a point $p$, I mean a set defined by $$\forall q : \|q-p\|\leq \epsilon$$
Here is a sample of Manhattan distance for $N = 16$
Edit (For some reason I cannot write comments on this machine or browser.)
The reason why I am interested in intersections of precisely 4 different areas (and not 3 or 5) is the 4 color theorem which I read about as a child and which I also read was proven with help of using computers.