Computational complexity of an algorithm
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. 180
,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. 835