If the OP is using GIS, it can be even easier.

Your first two steps are spot on, but then step three could simply be to add a large buffer for each capital and use some and/or/nor/xor (I'd have to look up to be certain) rules to have the buffer zones not overlap, but end where touching. Apply a color scheme and you're in business.