Next: Computing the Complement of Up: An Efficient Representation and Previous: Normalizing Spanning Intervals

## Computing the Intersection of Two Normalized Spanning Intervals

Given two normalized spanning intervals  and  , their intersection is a set of normalized spanning intervals whose extension is the intersection 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 one normalized spanning interval.

The intuition behind the above definition is as follows. All of the intervals in the extension of a spanning interval are of the same type, namely [q,r], (q,r], [q,r), or (q,r). The intersection of two spanning intervals has a nonempty extension only if the two spanning intervals contain the same type of intervals in their extension. If they do, and the sets contain intervals whose lower endpoint is bound from below by  and  respectively, then the intersection will contain intervals whose lower endpoint is bound from below by both  and  . The resulting bound is open or closed depending on which of the input bounds is tighter. Similarly for the upper bound on the lower endpoint and the lower and upper bounds on the upper endpoint.

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