I remember seeing something similar to https://www.jasondavies.com/maps/voronoi/capitals/. But the areas were weighted by the populations of the capitals. You ended up with something quite close to real political maps IIRC.