Finding line of best fit demarcating national borders

Question

Per title, what algorithms are available for defining borders for states (or other entities) based on certain nodes in the world (eg. cities or armies) with varying weights?

For example, there are three non-equidistant city-states and a bunch of military vehicles of varying strength nearby representing each city-states' military power. I would like to be able to draw a border that accounts for the fact city-state A has a huge great army on their outskirts, projecting their power outward.

Ideally the optimal algorithm would be able to calculate a series of connected lines with a high level of precision for multiple states and a large number of nodes (let's say three dozen, for the sake of argument). Speed isn't too much of a factor, since the results would be cached and I'd need to apply a function to 'curve' it anyway.

Answer 1

One solution that springs to mind is creating a Voronoi diagram. This will, in the original form, only take into account distance (although you can use different norms like manhattan or euclidean) which is not exactly what you want. I think though that you could tweak the algorithm to use some other heuristic like the one you mention, taking into account armies, economics or other factors.