This looks like a Voronoi tesselation, although it wasn't done that way.
Simply doing a Voronoi on a map projection (like Mercator) won't work, because (most) straight lines on such a projection are actually curved lines on the surface of the Earth, and vice-versa.
To get a more accurate picture, I used a Python script to generate a CSV. This script generates a regular grid with 0.5 degree spacing, and finds the closest capital for each point using the Vincenty formula.
Iceland and North Korea do quite well out this. Russia and the USA, less so.