The *span* of two intervals and , denoted
, is the smallest interval whose extension contains the
extensions of both and .
For example, the span of (1,4) and [2,6] is (1,6].
Similarly, the span of [3,7) and (3,7] is [3,7].
More generally, the lower endpoint of is the minimum of the
lower endpoints of and .
The lower endpoint of is open or closed depending on
whether the smaller of the lower endpoints of and is open or
closed.
Analogously, the upper endpoint of is the maximum of the
upper endpoints of and .
The upper endpoint of is open or closed depending on
whether the larger of the upper endpoints of and is open or
closed.
More precisely, can be computed as follows:

The notion of span will be used in Section 4.7.

Let us extend the notion of span to two sets of intervals by the following definition:

We will want to compute the span of two sets of intervals and , when both and are represented as spanning intervals. Additionally, we will want the resulting span to be represented as a small set of spanning intervals.

Given two normalized spanning intervals and , their *span*
is a set of normalized spanning intervals whose extension
is the span of the extensions of and .
One can compute as follows:

An important property of normalized spanning intervals is that for any two
normalized spanning intervals and , contains
at most *four* normalized spanning intervals.
In practice, however, fewer normalized spanning intervals are needed, often
only one.

The intuition behind the above definition is as follows. Consider, first, the lower endpoint. Suppose that the lower endpoints and of and are in and respectively. That means that and . The lower endpoint of will be , when , and , when . Thus it will be , for all , and will be , for all , where , when , and , when . Thus there will be two potential ranges for the lower endpoint of : and . When the lower endpoint of is taken from the former, it will be open or closed depending on whether the lower endpoint of is open or closed. When it is taken from the later, it will be open or closed depending on whether the lower endpoint of is open or closed. Thus the lower endpoint of can be either or . Analogous reasoning can be applied to the upper endpoints. If the upper endpoints of and are and respectively, then there are two possibilities for the upper endpoint of , namely and , where , when , and , when .

Wed Aug 1 19:08:09 EDT 2001