Graphics Reference
In-Depth Information
Definition.
The function F in Theorem 18.3.1 is called a
mean value form
for the
function f.
[Snyd92] proves that if a function satisfies a Lipschitz condition, then its mean
value form is of order 2, which means that it matches the function very well as the
width of intervals decreases. On the other hand, this is not the case for large inter-
vals and suggests that one should use different inclusion functions depending on the
size of the intervals. The point of the mean value theorem is to get a (linear)
approx-
imation
to a function. Therefore, use it for small intervals, but on large intervals use
a more direct inclusion function for f (one obtained perhaps by formulas such as
(18.1)). One important way to get good inclusion functions that are close to being
ideal functions is to make use of the regions over which they are monotone. This is
what gave us an answer in Example 18.2.10.
18.4
Constraint Solutions
This section presents the first of three interval analysis algorithms described in
[Snyd92], which have applications to a number of important problems in geometric
modeling.
Constraints on a set of points in
R
n
can usually be translated into a function
n
f
:
RR
Æ
with the property that
()
= 1,
f
x
if
the point satisfies the constraints,
x
= 0,
otherwise.
An inclusion function F for f will take on values [0,0], [1,1], or [0,1].
Definition.
An element A ΠI(
R
n
) will be called an
infeasible
,
feasible
, or
indeterminate region
for F if F(A) = [0,0], F(A) = [0,0], or F(A) = [0,1], respectively.
No points satisfy the constraints in an infeasible region, all points satisfy them in
a feasible region, and points may or may not satisfy the constraints in an indetermi-
nate region.
In applications it is also useful to have an additional function
(
)
Æ
{}
n
hI
:
01
,
,
called a
set constraint
function, which tells us whether to accept an indeterminate
region as a solution. Actually, we shall use an inclusion function H for h, called a
solution acceptance set constraint
function. We have the following interpretation:
()
=
[ ]
()
=
[]
()
=
[]
H A
00
01
11
,:
subdivide A
,
H A
,:
subdivide A
,
H A
, :
accept
A as a solution.
