Graphics Reference
In-Depth Information
CHAPTER 18
Interval Analysis
18.1
Introduction
Interval analysis is one approach to deal with numerical errors in computations. To
give an oversimplified account, it addresses a common situation in numerical com-
putations. One has some variables that one only knows to a certain accuracy (the
values lie in certain intervals) and one wants to perform some operations on them.
The result therefore will only be approximate (all one can say is that it lies in some
interval of values). Since we cannot assume to ever have exact numbers, we want to
replace them by intervals and formalize the idea of functions from intervals to inter-
vals. Accuracy would be specified by changing the size of the input intervals. We no
longer guarantee exact numbers but instead guarantee that numbers, either input or
output, lie in specified intervals. Geometric computations on a computer tend to
always include some epsilons anyway and interval analysis simply formalizes the use
of these epsilons.
Although interval analysis has a long history, Moore's monograph [Moor66] began
a new era of applications to error analysis for digital computers. There is a large body
of literature on the subject. It is not the goal of this chapter to present a thorough
development of interval analysis. Rather, we have a much more modest goal to simply
present some of its basic elements and indicate its relevance to obtaining robust algo-
rithms in geometric modeling. In particular, one reason for including this material in
this topic was the author's interest in the generative modeling approach described in
[Snyd92]. Interval analysis played a big role in Snyder's GENMOD modeler. A large
part of the topic [Snyd92] is devoted to showing how interval analysis can be used in
algorithms important for geometric modeling. See also [Snyd92a] for a quick
overview. Two other general references are [Moor79] and [AleH83]. For extensive
bibliographies see [Garl85] and [Garl87].
Sections 18.2 and 18.3 present the basic definitions in interval analysis, list the
most important properties of arithmetic with intervals, and discuss inclusion func-
tions. Sections 18.4-6 describe several interval analysis algorithms that lead to robust
solutions for many problems in geometric modeling. We finish with a few concluding
remarks in Section 18.7.
