Complexity of an algorithm for bounding a region in 2D

Question

First I apologize if the title is unclear, but I didn't find anything better.

I'm solving a differential equation that has two parameters , here denoted by points of a plane.These parameters are real numbers. For some points of the plane (or, equivalently, for some parameters of the differential equation) , the solution of the equation satisfies some condition and we denote such points of the plane with 1. This points make a simply-connected region in the plane, and I know that this region lies somewhere in $0<x<1.6, -.7<y<.3$ rectangle. My goal is to find this region.Remember that this region is on the real plane.($\mathbf R^2$)

My main question is this: I already know these two things about the wanted region:

1. The set of points on the plane that satisfy the conditions (the wanted region) , form a simply-connected region

2. This region lies somewhere in $0<x<1.6, -.7<y<.3$ rectangle

for example it may be something like this:

I want to use this two facts to find the region with less computations; i.e. instead of checking the condition on all points on the rectangle, actually , on a very high-resolution grid (this the first approach below), use an algorithm (below : Variant 2) that more quickly converges to the boundary (and so determines the region without inspecting all points).

(If you know a better approach ,I'll be happy to hear)

Variant 1 (the naive approach, noted above)

Divide each axis to identical steps (of length $\Delta$ ) and check the condition on each node to find the region.$\Delta$ must be as small as possible to find the region with an acceptable accuracy ($\Delta0.001$ suffices for my purpose) . (in the picture : nodes = intersections). This method needs a huge number of check operations , but can be used to find all kinds of regions; I mean if I didn't know that the wanted region is connected or it had sharp edges, etc. ,this method was the only way.

Variant 2

(It may be a famous method, but I haven't seen it before)

Because the region will be simply connected, it suffices to find its boundary .We use a recursive approach. We start from a grid (like the first step, but with much larger distance between nodes, say, $100\Delta$) and check the condition on this grid.For the next step, I assume the interval between two adjacent 1s is 1 everywhere and between two adjacent 0s is 0 everywhere. If two adjacent nodes gave different results (1 on one them and 0 on the other) , I put a point between them and check the condition on that point (red points in the picture) check this point. If it was 1, I put a new point between this point and the adjacent 0 and check that point; and if it was 0, I put a new point between this zero and adjacent 1 and check that point. I continue till I arrive at a distance of $\Delta$ between points.So I've found the boundary. (This method is like bisection method for finding the roots of a function)

In the picture, the first iteration is shown.Black and yellow points are the points of the initial grid (that are distributed on the whole rectangle) and red points are those that are added after checking the initial grid nodes. Black points are points that are determined to satisfy the condition (are 1) and so are certainly inside the region. Yellow points are those that did not satisfy the condition and so are outside, and red points are those added in the 2nd iteration , between adjacent nodes with different results (between a 1 and a 0) ,according to the above paragraph.

So , using this method I've found the region with the same accuracy as in the first method, and saved a lot of time too.

I want to know how much this method is faster. A qualitative answer that shows if it is better to implement this method , suffices. My problem is so computational intensive that I can't use the first approach.

Answer 1

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.)

Answer 2

This answer addresses the edited question (which is a bit different now).

If you want to know which of those two methods is faster on your problem instances, the best strategy is going to be to implement them both and try them both on your problem instances. No one here is going to be able to tell you the answer. Complexity-theoretic worst-case asymptotic running time analysis is not likely to be the best tool here to tell you how much better the second one is in practice. Instead, try some experiments and see how much faster it actually is!

Keep in mind it is possible that the second method might fail to find all of the region, depending upon how sharply curved (and how concave) the perimeter is. The first method could also fail, too, if the region is unpleasant enough. For instance, if the region has a very thin and long peninsula jutting out, and if that peninsula does not intersect any of your grid point, you will not detect the peninsula. That might be acceptable, given that your method is only intended as an approximation -- or it might not arise in practice, for the specific differential equations you are using -- but in principle, it could happen. Any worst-case complexity-theoretic analysis is going to have to assume that it does happen.