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 .