next up previous
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  tex2html_wrap_inline9216 and  tex2html_wrap_inline9218 , their intersection tex2html_wrap_inline9704 is a set of normalized spanning intervals whose extension is the intersection of the extensions of  tex2html_wrap_inline9216 and  tex2html_wrap_inline9218 . One can compute tex2html_wrap_inline9704 as follows:

displaymath1584

An important property of normalized spanning intervals is that for any two normalized spanning intervals  tex2html_wrap_inline9216 and  tex2html_wrap_inline9218 , tex2html_wrap_inline9704 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  tex2html_wrap_inline9726 and  tex2html_wrap_inline9728 respectively, then the intersection will contain intervals whose lower endpoint is bound from below by both  tex2html_wrap_inline9726 and  tex2html_wrap_inline9728 . 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