Interval Analysis - Computer Graphics and Geometric Modeling - page 732

(1) Since the algorithm needs to terminate, how do we handle indeterminate regions?
(2) How should we divide intervals?
(3) Some problem have a finite set of points as their solution. Our algorithm pro-
duces a collection of intervals. How can we group these intervals so that each
union of these groups contain a unique point from the solution?

The problem of indeterminacy is that indeterminate regions may contain a solu-
tion or they may not. Sometimes one way to handle this problem is to replace equal-
ity constraints with inequality constraints. For example, rather than checking for
collisions of objects, we could check if they get sufficiently close. Another approach
that works if we know that there are single solutions is to use a solution acceptance
set constraint based on the size of regions. We quit if they get small enough.
A typical approach to subdividing intervals is to divide along each individual coor-
dinate in a cyclic fashion. This means that we divide an interval in R n by bisecting
the x 1 -axis interval in one iteration, then the x 2 -axis interval in the next iteration, and
so on. After we have subdivided the x n -axis interval, we start back with the x 1 -axis
interval again. Other methods can be used however.
The solution to Algorithm 18.4.1 is a collection S of intervals. It is often useful to
group these together into lists that make up the connected components of the solu-
tion set. The function Components in Algorithm 18.4.2 does that and also converts
the components into intervals, the list of which we then return. We are assuming that

interval list function Components ( interval list S)
begin
interval list C;

Initialize C to empty;
for each A in S do C := Merge (A,C);
return C;
end ;

interval list Merge ( interval A, interval list C)
begin
for each B in C do
if (B « A) π f then
begin
A := A ⁄ B;
Delete (B,C);
end ;
Insert (A,C);
return C;
end ;

Algorithm 18.4.2. Merging intervals into components.