I very much agree with Ilmari Karonen's answer, and believe that the best solution here might be to generate more solutions to the problem, perhaps breaking away from assumptions you're making. Might I humbly suggest one that seems consistent with how your game appears to work.

I propose you could make territory acquisition work the same way: ownership of a given point of territory is determined by the building or unit closest to it. Essentially, when you draw/figure out territory ownership, you draw a Voronoi diagram with a marked point for each unit and building on the map. To keep territory from extending too far (and avoid having to potentially query every single unit in the game), impose a maximum distance for which a unit can be considered, either a fixed distance, or something similar to your scaling idea where the region of influence grows as you rank up.

• You had better make sure those units and buildings can be queried efficiently, especially if you have a scaling maximum distance. Using something like a quad tree, even in the database layer, is a must here.
• Gameplay would be slightly different: in order for a player to keep claim on territory, they would have to leave a building behind. You could probably make a cheap building for expressly this purpose, though, such as a flag.
• Depending on user feedback, you may need to account for geological features anyway. For instance, in the aforementioned river example, you may find that the results are really ugly when the territory line doesn't quite mesh with the river, so you'll want to make it a boundary of some kind for the distance calculations.
• Calculating exactly how much territory a person owns would be more difficult, because you'd have to consider all of the units on the field instead of just counting squares. It would be hard to give users a real-time update for how much territory they own, and you would need an efficent way to calculate an estimate on the server in order to grant rewards based off of it (essentially, you would need to draw a Voronoi diagram of the world on it either every few hours or when requested by users). Doing this might require you to supply your server(s) with GPUs, incurring additional hosting costs.

I very much agree with Ilmari Karonen's answer, and believe that the best solution here might be to generate more solutions to the problem, perhaps breaking away from assumptions you're making. Might I humbly suggest one that seems consistent with how your game appears to work?

I propose you could make territory acquisition work the same way: ownership of a given point of territory is determined by the building or unit closest to it. When someone tries to build a building, you simply figure out who owns the closest unit or building to it - if it's the current player, you let them build the building. When you want to highlight who owns what territory on the screen, you draw a Voronoi diagram with a marked point for each unit and building in the immediate area. To keep territory from extending too far (and avoid having to potentially query every single unit in the game), you'd impose a maximum distance for which a unit can be considered, either a fixed distance, or something similar to your scaling idea where the region of influence grows as you rank up.

• You had better make sure those units and buildings can be queried efficiently, especially if you have a scaling maximum distance. Using something like a quad tree, even in the database layer, is a must here.
• Gameplay would be slightly different: in order for a player to keep claim on territory, they would have to leave a building behind. You could probably make a cheap building for expressly this purpose, though, such as a flag.
• Depending on user feedback, you may need to account for geological features anyway. For instance, in the aforementioned river example, you may find that the results are really ugly when the territory line doesn't quite mesh with the river, so you'll want to make it a boundary of some kind for the distance calculations.
• Calculating exactly how much territory a person owns would be more difficult, because you'd have to consider all of the units on the field instead of just counting squares. It would be hard to give users a real-time update for how much territory they own, and you would need an efficient way to calculate an estimate on the server in order to grant rewards based off of it (essentially, you would need to draw a Voronoi diagram of the world on it very few hours, like a global census). Doing this might require you to supply your server(s) with GPUs, incurring additional hosting costs.

ADDENDUM: For something easier to calculate on a global scale, you could make it so that only buildings determine territory acquisition (i.e. marching units do not claim territory, but must build a building first). This makes it a lot easier to calculate global territory acquisition (since buildings normally don't move), but does come with some caveats:

• The fact that you have to build a building to acquire territory may be unworkable for your game's design. If it does work for you, you may find that you either need simple buildings to satisfy these requirements (such as flags), units that can still claim territory (perhaps a "commander" unit), or exceptions to the territory claim rule (such as being able to build on unclaimed territory, or perhaps a "campfire" building that can be built anywhere, including in enemy territory).
• You will probably also have to implement a maximum range of influence, so that you can feasibly have territory owned by no one. Otherwise, it becomes impossible for players to build if they don't have a building already.
• You wouldn't get the "cool" effect of territory acquisition following combat lines. You could probably calculate with units on a local scale and use global scales for the census, though.