I don't know how NaytaData made it, but if I were doing it, I would do something like this:

• start with a "blank" un-coloured map of coastline and country borders
• put all the "capital" cities on the map
• make a temporary grid of points over the map and find the closest city for each point
• paint the map based on those temporary grid points

I would use a computer but the same steps would work with paper & pen.