next up previous
Next: Computing the Span of Up: An Efficient Representation and Previous: Computing the Intersection of

Computing the Complement of a Normalized Spanning Interval


Given a normalized spanning intervals  tex2html_wrap_inline8292 , its complement  tex2html_wrap_inline9736 is a set of normalized spanning intervals whose extension is the complement of the extension of  tex2html_wrap_inline8292 . One can compute tex2html_wrap_inline9736 as follows:


An important property of normalized spanning intervals is that for any normalized spanning interval  tex2html_wrap_inline8292 , tex2html_wrap_inline9736 contains at most seven normalized spanning intervals.

The intuition behind the above definition is as follows. First note that the negation of tex2html_wrap_inline9186 is tex2html_wrap_inline9748 . Next note that the extension of  tex2html_wrap_inline8292 contains intervals whose endpoints q and r satisfy tex2html_wrap_inline9756 . Thus the extension of tex2html_wrap_inline9736 contains intervals whose endpoints satisfy the negation of this, namely tex2html_wrap_inline9760 . Such a disjunction requires four spanning intervals, the first four in the above definition. Additionally, if the extension of  tex2html_wrap_inline8292 contains intervals of the form [q,r], the extension of tex2html_wrap_inline9736 will contain all intervals not of the form [q,r], namely (q,r], [q,r), and (q,r). Similarly for the cases where the extension of  tex2html_wrap_inline8292 contains intervals of the form (q,r], [q,r), or (q,r). This accounts for the last three spanning intervals in the above definition.

We now see why it is necessary to allow spanning intervals to have open ranges of endpoint values as well as infinite endpoints. The complement of a spanning interval, such as [[i,j],[k,l]], with closed endpoint ranges and finite endpoints includes spanning intervals, such as tex2html_wrap_inline9786 , with open endpoint ranges and infinite endpoints.

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