I may be wrong, but the idea that all territory needs to be "claimed" and ringed about with imaginary lines, no matter what the facts on the ground happen to be, seems to be a fairly recent and specifically Western Europe conceit. AFAIK, the compulsion to draw lines all over the map representing political borders originated there.
While other societies (particularly those whose economies were based upon agriculture) recognized property boundaries, as well as territories attached to centers of population and even had vague ideas of larger regions (which were, in hindsight, almost never very precise), the idea that a state needs to claim sole sovereignty over all territory within a certain geographic region, even empty and unpopulated territory lacking in any economic or strategic value, strikes me as fairly modern.
Plus, any pastoral or nomadic groups aren't going to see any value in restricting themselves within such borders.
So, in essense, this shouldn't be that difficult a challenge - there are any number of ways that one can approach it.