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.
Have you ever heard of a Voronoi diagram?
The basic idea is that, given a set of marked points on a field, each unit of area on that field is colored according to the marked point closest to it, with the result being an interesting emergent "mosaic" structure. More interesting patterns appear if the marked points are allowed to name their own colors and share colors with other points - you could imagine, say, in a field with red points on the left and yellow points on the right, a diagram with a red region on the left and a yellow region on the right with a jagged line in between depending on the points' arrangements.
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.
A really cool pro to this approach is that territory acquisition becomes incredibly natural. For instance, if you have two armies fighting across a river (or other natural barrier), the territory acquisition pattern will more or less follow the river. If you have a small player marching into a much larger player's territory, the territory acquisition pattern will show the first player controlling a small enclave immediately around them. All of this works at any (continuous) zoom level, and it's all possible with not only not having to consider geological features separately, but also not even having to consider territory as a permanent entity at all - it is simply a function of the units and buildings currently on the field.
(As another plus, the lack of hard territory divisions also makes it easy to account for the fact that the world is round, allowing the game to be played just as well around the poles and avoiding inaccuracies caused by 2D map projections.)
Of course, there are some cons to consider, too:
- 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.