Border between terrain areas in 3D strategy game

Question

I want to make dynamically generated border between opponent areas on the plain terrain with some points ("bases") (e.g. alien and human bases) in the 3d strategy game. Each base has its own "land of influence" so the border should go on the appropriate distance between conflicting bases. If you have played Settlers I,II etc, you should to understand what I actually mean.

So I have an array of base coords and want to get array of polylines, describing these borders.

Please, can you suggest me any solution for it (may be some algorithms or even ready packages).

Example of desired border:

Answer 1

It sounds like you want a Voronoi diagram. Below is a 2D diagram, but the same algorithm also works in 3D.

Answer 2

I think you might want to look into a suitably weighted Voronoi diagram. In standard VDs, only the distance to the nearest control point matters to determine cells, but from your example it looks like you want control points to have an influence even when they are not the closest point.

For example, there is a region to the left of your highest blue point which is in the red area despite the closest control point being blue:

I assume this is because the NW-most red point exerts an influence, as shown by the arrow.

The 'review' linked from that wikipedia page, and the Google image search results for weighted Voronoi diagram, suggest that this kind of influence, resulting in rounder boundaries, is achievable, though obviously further research awaits you.