Re: Tetrits, just checking FTIA...
Nate et al,
Just to be a bit picky; also, please clarify:
On 4/11/2010 11:08, Nate Hayes wrote:
Dan Zuras Intervals wrote:
One thing to keep in mind is that interval branch-and-prune methods are
an application of the Nested Intervals Theorem, which says the
intersection of infinitely many nested intervals over a non-empty
compact (closed and bounded) domain is a non-empty set. If the width of
the nested intervals are decreasing, the intersection is a unique real
number.
Actually, the widths have to be decreasing at a particular rate. For
example, take
\x_i = [1-1/2^i,2+1/2^i]
The intervals are nested and their widths are decreasing, but the
intersection is [1,2], not a point.
In any case, I don't think this fact was entirely relevant to
your point.
So it is not possible that an empty interval can ever arise in a
divide-and-conquer method so long as the original input domain meets
these criteria.
I'm not sure I understand the context you are describing. In particular,
what if I use an interval Newton method or constraint propagation
to reduce the size of the box, and this results in a box which
has empty intersection with the original box. That original box
would then be considered to be fathomed, but we may wish to
use our standardized arithmetic to detect that the intersection
is empty. Similarly, during constraint propagation (an integral
part of many branch and bound algorithms), an empty interval
may be produced as an intermediate result, and it is possible we
don't detect it immediately.
Now, Nested Intervals Theorem does _not_ hold if the input domain is
empty or unbounded. So these probably are the kinds of examples we
realistically will want to examine very closely.
???
Nate
--
---------------------------------------------------------------
R. Baker Kearfott, rbk@xxxxxxxxxxxxx (337) 482-5346 (fax)
(337) 482-5270 (work) (337) 993-1827 (home)
URL: http://interval.louisiana.edu/kearfott.html
Department of Mathematics, University of Louisiana at Lafayette
(Room 217 Maxim D. Doucet Hall, 1403 Johnston Street)
Box 4-1010, Lafayette, LA 70504-1010, USA
---------------------------------------------------------------