# Finding line of best fit demarcating national borders

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.

• If you work on some kind of a grid.. "childhood" memories remind me of the smell of this monster: www2.imm.dtu.dk/~mbs/downloads/levelset040401.pdf . You could seed fronts from clusters of units, march the fronts based on a weight function and then get a discrete version of the borders. Ideally, the fronts will intersect and merge if the clusters are packed and have a sufficiently high weight associated to them. Or you could take an energy-based approach and apply a rubber band that contracts wrapping around your units (with buffer radii for the weights). Aug 16, 2012 at 17:01

## 1 Answer

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.

• Looks like there are many variants of the Voronoi diagram, including weighted ones: nirarebakun.com/voro/emwvoro.html Had a look at a couple of papers and I'm sure there's one or two things that will work. Cheers! Aug 17, 2012 at 8:24