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.
I’m curious as to what projection this is mapped on. It seems very… Horizontal.