Graphics Reference
In-Depth Information
The case H(A) = [0,0] is usually best handled with the function F, because for isotone
functions no intervals B Õ A would ever be accepted. On the other hand, there are
functions, like w(A) < d, which are not isotone.
Algorithm 18.4.1 is a generic solution to the constraint solution problem. Variants
of the algorithm are useful in certain cases.
18.4.1 Theorem.
If Algorithm 18.4.1 does not find a solution, then there is not one.
Also, the constraint solution algorithm converges to the actual solution if inclusion
functions in the equality and inequality constraint are convergent.
Proof.
See [Snyd92].
Some issues addressed in [Snyd92] regarding the use of Algorithm 18.4.1 are
interval list function
ConstraintSolution (
inclusion function
F,
inclusion function
H,
interval
A)
{ F is the inclusion function for a constraint function f. H is the inclusion function
for an solution acceptance set constraint function. }
begin
interval list
S;
{ the solutions }
interval list
L;
interval
B, B
1
, B
2
;
S := f;
L := ( A );
while not
(Empty (L))
do
begin
B := AnyElementOf (L);
case
F (B)
of
[1,1] : Insert (B,S);
[0,0] : ; { Discard B }
[0,1] :
if
H (B) = [1,1]
then
Insert (B,S)
else
begin
Subdivide (B,B
1
,B
2
); { Subdivides the interval B }
Insert (B
1
,B
2
,L);
end
end
end
;
return
S;
end
;
Algorithm 18.4.1.
The constraint solution algorithm.
