# Complexity of an algorithm for bounding a region in 2D

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.

• What's 0 what is 1 in inputs? I think you should be more precise in problem definition.
– user742
May 27 '13 at 11:16
• Actually I solve a DE for each input, and 1 means stable and 0 means unstable. I will edit the question. May 27 '13 at 11:18
• I don't know what is DE, what is stable node and what is unstable node? please be clear, put your definitions into the question. I can guess what's your problem and what's your solution, but for example if I forced to guess 3 times and each time I guess correctly with 1/2 probability, means I understand your problem with 1/8 probability. This happens not just for me, for many member of this site. You can provide a link to your definitions.
– user742
May 27 '13 at 11:24
• You tell us that you're solving a differential equation in order to evaluate the condition for a particular point, but you're not using this information in your algorithm, and your algorithms are too sketchy to guarantee a correct solution. You will either need to use more information about the equation or use a more careful way to explore and subdivide your grid cells, or they may fail to find the region altogether. May 27 '13 at 13:24
• @user215721 Only when you know how small enough is, and you will still need to know in which area to look. If your distance is too big or your area is wrong you may miss the region; if it's much too small and the area much too large you may loose a ridiculous amount of time searching. The more fundamental problem is that the region may be arbitrarily far removed from the point where you start looking. In other words: any fixed 'small enough distance' and 'large enough area' may completely fail. May 27 '13 at 13:59

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

• Thank you for your attention. Please read the question again, I made it more clear.The approach you mentioned is indeed my first approach in the question: to check all the plane (a limited rectangle actually) with the maximum possible accuracy (minimum reachable $\epsilon$ in your terminology and minimum reachable $\Delta$ in my terminology in the question). You are right: the plane is Real plane ($\mathbf R^2$) and so the region has a continuous boundary, and sweeping the whole rectangle that contains the region is the simplest but.... (read the next comment,the length exceeds the max) May 28 '13 at 12:08
• ...but most computational intensive (though most confidential) approach. I can't use this approach duo to computational cost of the problem. So I want to use the 2nd approach that uses the known fact that the region will be simply-connected, and just try to find the boundary instead of sweeping the whole rectangle. May 28 '13 at 12:09

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.

• Please take a look at this question. May 28 '13 at 21:34