A random distribution of points lies on a map.

This data lies behind an API, and I want to grab the complete set of points within a given bounding box.

I can query the API with the bounding box and the API will return the set of points that fall within that box.

The problem is that the API will limit the result set to 10 items, with no pagination and no indication if there are more points that have been omitted.

So I made a recursive algorithm that takes a bounding box and requests the points that lie within it. If the result set is exactly 10 items, then I split the bounding box into four quadrants and recurse.

It works fine but my question is this: if want to minimize the number of API calls, what is the optimal way to split the bounding box?

Splitting it into quadrants was just an arbitrary decision. When there are a lot of points on the map, I have to drill down many levels before I start getting meaningful results. So I imagine it might be faster to split the box into, say, 9, 16, or more sections. But if I do that, then I eventually get to a point where a lot of requests are returning 0 results which isn't so efficient.

Also, does the size of the limit on the results set affect the answer?

(This is all assuming that I have no prior knowledge of nominal point density in the bounding box)