Next: Computing the of a Up: An Efficient Representation and Previous: Computing the Complement of

## Computing the Span of two Normalized Spanning Intervals

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 .

Next: Computing the of a Up: An Efficient Representation and Previous: Computing the Complement of

Jeffrey Mark Siskind
Wed Aug 1 19:08:09 EDT 2001