Complexity of an algorithm for bounding a region in 2D
This question is not well-posed.  You haven't told us what form you want the answer in, nor what you know about the region.  In the fully general case, this problem is not solvable in any finite amount of time: there are uncountably many possible regions, so you can't even describe all of them in finite space.

Perhaps what you want is an approximation to the region (or to its perimeter).  If so, you need to figure out how you want it to be described, and what approximation metric you are using.

A plausible approach is to find a bounding box, then sweep a vertical line from left to right.  If your region is convex, then given the vertical line $x=1$ (say), you can find all points on that line that lie within your region by using binary search (twice): the result will be that all points $(x,y)$ satisfying $x=1$, $f(1)\le y \le g(1)$ are in the region, for some values $f(1),g(1)$.  Now if you know that all of the points in your region lies satisfy $1 \le x \le 5$, you can iterate over values of $x$, from $1$ to $5$ by steps $\epsilon$, and find the values of $f(x)$ and $g(x)$ for each such $x$.  This gives you about $8/\epsilon$ points on the perimeter of the region.  Now, you could interpolate along these points somehow to get a plausible approximation to the shape of the region.

Whether this is good enough will depend upon your particular application and what you are trying to accomplish.  Since you haven't told us that, we can't evaluate whether this is an adequate solution for your needs.  (That, incidentally, is why the question is not well-posed.)