Various Topics on Programming

..s..

"Vista" <abc@gmai.com> wrote in message
news:f4nt8b$ehg$1@news.Stanford.EDU...
> automatic parametric space exploration and boundary detection.
>
> Hi all,
>
> I am not sure where to ask about my "strange" question, so as an initial
> attempt, I post it here.
>
> I have a parameterized function f(x, y, z, u, v), which takes values on
> {0,
> 1}, i.e. either 0 or 1.
>
> Through experimenting I've found that when plotting out in 2D there is a
> clear linear cut in the parameter space.
>
> If I plot f(1, y, z, 5, 7) as a mesh of grid size 0.1, the cut is a
> straight
> line, the region below this line has f=1, and the region above this line
> has
> f=0.
>
> If I plot f(2, y, z, 5, 7) as a mesh of grid size 0.1, the cut is a
> straight
> line, the region below this line has f=1, and the region above this line
> has
> f=0. The only difference is that this line shifted.
>
> ...
>
> If I plot f(x, 1, z, 5, 7) and f(x, 2, z, 5, 7) etc., still there is a
> linear cut splitting the space.
>
> ...
>
> If I plot f(x, y, 1, 5, 7) and f(x, y, 2, 5, 7) etc., still there is a
> linear cut splitting the space.
>
> ...
>
> It looks like there is a space-cutting plane in my parameter space.
>
> But the grid size is 0.1, I still have a hard time figuring out what will
> happen when grid size becomes 0.01 and 0.001, etc.
>
> But still, I would like to discover how to define this cutting plane
> mathematically... ba
>
> My function is too complicated, and can only be computed numerically, so I
> had a hard time finding a closed form for this cutting plane.
>
> Is there a way to determine the cutting plane using some automatifc
> procedure?
>
> I mean, it looks like some kind of optimization procedure, it seeks the
> finest boundry in the space such that on the left of the cut, f=1 and on
> the
> other side of the cut, f=0. It also looks like a regression problem. But
> so
> far I am still not sure how to model it.
>
> Can anybody give me some suggestions and comments?
>
> Thanks a lot!
>
>

Let me describe my problem with an simpler example.

Let's say I have a 2D plane.

I draw a straight line to split the plane to two parts: Left and Right. The
equation for the straightline is y=a*x+b.

In the left part the values of F(x, y) are 1s, while in the right part the
values of F(x, y) are 0s.

You can query the value of F for any x and y. That's to say, you give me a
location (x, y), I will tell you the function value F(x, y).

What's the most efficient way to discover the value of "a" and "b"?

..n ..o..

"Vista" <abc@gmai.com> wrote in news:f4pa2e$rg2$1@news.Stanford.EDU:

>
> "Vista" <abc@gmai.com> wrote in message
> news:f4nt8b$ehg$1@news.Stanford.EDU...
>> automatic parametric space exploration and boundary detection.
>>
<snip>
>>
>>
>> It looks like there is a space-cutting plane in my parameter space.
>>
>> But the grid size is 0.1, I still have a hard time figuring out what
>> will happen when grid size becomes 0.01 and 0.001, etc.
>>
>> But still, I would like to discover how to define this cutting plane
>> mathematically... ba
>>
>> My function is too complicated, and can only be computed numerically,
>> so I had a hard time finding a closed form for this cutting plane.
>>
>> Is there a way to determine the cutting plane using some automatifc
>> procedure?
>>
>> I mean, it looks like some kind of optimization procedure, it seeks
>> the finest boundry in the space such that on the left of the cut, f=1
>> and on the
>> other side of the cut, f=0. It also looks like a regression problem.
>> But so
>> far I am still not sure how to model it.
>>
>> Can anybody give me some suggestions and comments?
>>
>> Thanks a lot!
>>
>>
>
> Let me describe my problem with an simpler example.
>
> Let's say I have a 2D plane.
>
> I draw a straight line to split the plane to two parts: Left and
> Right. The equation for the straightline is y=a*x+b.
>
> In the left part the values of F(x, y) are 1s, while in the right part
> the values of F(x, y) are 0s.
>
> You can query the value of F for any x and y. That's to say, you give
> me a location (x, y), I will tell you the function value F(x, y).
>
> What's the most efficient way to discover the value of "a" and "b"?

I can imagine that any simplex or pattern search type technique might be
useful. It will be able to approach but never reach "a" and "b".

Suppose I take two pairs of points (P, Q) and (U, R) such that points P
and Q are "in" the region, and U and R are "out of" the region. I
basically have a quadrilateral (P, Q, U, R) which "lies" along the
cutting line.


+
+
+
+
P----------+----R
| + |
| + |
| + |
| + |
| + |
| + |
| + |
Q------ + |
---+----- |
+ ---U
+
+
+
+
+



For any quadrilateral like this, we can "search" along the lines that
cross the cutting line ( Q<->U and P<->R ) and find a thinner
quadrilateral. We can also "extend" the quadrilateral along the cutting
line to make it "longer".

Each time we take either of these steps, we get a quadrilateral that gets
closer and closer to being straight along the cutting line. However, it
will never "reach" it, since we can do this forever. It will converge to
it and so we can get "a" and "b" to some arbitrary precision which is
probably good enough.

(There's probably a simplex search using a triangle where any two corners
are in the same region. Ultimately, this should wind up with a triangle
that converges to the line.)

Of course, this ***ume that there is a straight line that is cutting the
plane! The moves outlined above don't work too well if the boundary is
not defined by a straight line.

However, I think using a more capable set of search rules could produce
an ever-more-accurate representation of the boundary (even in multiple
dimensions)... as long as the boundary is "smooth" at some scale.

For the 2D example again, if we have a quadrilateral as described above,
we can search not only along the Q<->U and P<->R lines that cross the
boundary, but we can also search along the lines P<->Q and R<->U running
"parallel" to the boundary.

+
+
+
+
P-------------+-R
| + |
| +|
| ++
| | +
| ++ | +
| + + | +
| + ++++++
Q------ + |
---+----- |
+ ---U
+
+
+
+
+



If the boundary is "spiky" then we're unlikely to hit a spike searching
along P<->Q or R<->U. If it's a smooth curve then we're much more likely
to find a point on the opposite side of the boundary. We could, for
example, add a point (or two) to our shape...


+
+
+
+
P-------------+-R
| + \
| + \
| ++ \
| + \
| ++ + G
| + + + /
| + ++++++ /
Q------ + /
---+----- /
+ ---U
+
+
+


.... so that the polygon still encloses some region of the boundary. We
can then search along the lines P<->R, P<->G, Q<->G and Q<->U to
"tighten" the polygon to the boundary, and search along P<->Q, R<->G and
G<->U to check that it hasn't "burst out".

If the starting polygon contains a region of the space that is
"interesting", then I think something like that procedure will produce a
shape that approximates the boundary within that region.

This probably works "better" when starting with a triangle and adding new
points as needed.

I think this kind of search also works in 'n' dimensions, the number of
points in the starting shape being at least (n+1)... but I have problems
visualising more than 3!

Ian Woods

....

On Jun 13, 1:38 pm, "Vista" <a...@gmai.com> wrote:
> "Vista" <a...@gmai.com> wrote in message
>
> news:f4nt8b$ehg$1@news.Stanford.EDU...
>
>
>
>
>
> > automatic parametric space exploration and boundary detection.
>
> > Hi all,
>
> > I am not sure where to ask about my "strange" question, so as an initial
> > attempt, I post it here.
>
> > I have a parameterized function f(x, y, z, u, v), which takes values on
> > {0,
> > 1}, i.e. either 0 or 1.
>
> > Through experimenting I've found that when plotting out in 2D there is a
> > clear linear cut in the parameter space.
>
> > If I plot f(1, y, z, 5, 7) as a mesh of grid size 0.1, the cut is a
> > straight
> > line, the region below this line has f=1, and the region above this line
> > has
> > f=0.
>
> > If I plot f(2, y, z, 5, 7) as a mesh of grid size 0.1, the cut is a
> > straight
> > line, the region below this line has f=1, and the region above this line
> > has
> > f=0. The only difference is that this line shifted.
>
> > ...
>
> > If I plot f(x, 1, z, 5, 7) and f(x, 2, z, 5, 7) etc., still there is a
> > linear cut splitting the space.
>
> > ...
>
> > If I plot f(x, y, 1, 5, 7) and f(x, y, 2, 5, 7) etc., still there is a
> > linear cut splitting the space.
>
> > ...
>
> > It looks like there is a space-cutting plane in my parameter space.
>
> > But the grid size is 0.1, I still have a hard time figuring out what will
> > happen when grid size becomes 0.01 and 0.001, etc.
>
> > But still, I would like to discover how to define this cutting plane
> > mathematically... ba
>
> > My function is too complicated, and can only be computed numerically, so I
> > had a hard time finding a closed form for this cutting plane.
>
> > Is there a way to determine the cutting plane using some automatifc
> > procedure?
>
> > I mean, it looks like some kind of optimization procedure, it seeks the
> > finest boundry in the space such that on the left of the cut, f=1 and on
> > the
> > other side of the cut, f=0. It also looks like a regression problem. But
> > so
> > far I am still not sure how to model it.
>
> > Can anybody give me some suggestions and comments?
>
> > Thanks a lot!
>
> Let me describe my problem with an simpler example.
>
> Let's say I have a 2D plane.
>
> I draw a straight line to split the plane to two parts: Left and Right. The
> equation for the straightline is y=a*x+b.
>
> In the left part the values of F(x, y) are 1s, while in the right part the
> values of F(x, y) are 0s.
>
> You can query the value of F for any x and y. That's to say, you give me a
> location (x, y), I will tell you the function value F(x, y).
>
> What's the most efficient way to discover the value of "a" and "b"?

Interesting problem, but there's not enough information here to answer
it. If the x-y plane is continuous, then infinitely many probes won't
be enough to answer the question. If "filled with 1's and 0's"
implies the "plane" is made of discrete postings, then there are two
further possibilities. If the plane is infinite (has infinitely many
posts), you need infinitely many probes to get a precise answer. On
the other hand, if the plane is finite, there are in general
infinitely many possible (a,b) pairs for each ***ignment of 1's and
0's.

If you meant that the plane is made of finite postings arranged on a
grid, it's easy to find the answer in O(n) time where n is the number
of postings on the biggest grid edge. Go around the outside of the
grid to find the two transitions 0-1 and 1-0. These give you the
first 2 edges of a Manhatten polygon that must contain the line.
Trace the rest of the polygon by following the 1-0 boundary. Finding
one or more (a,b) pairs for lines that pierce only the original edges
and otherwise lie inside the polygon is pretty simple, and I leave it
to you. Of course you can trace out the polygon and find the (a,b) at
the same time, so the polygon never need be stored.