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

Normalizing Spanning Intervals

Just as we desire that the extension of every interval have a unique representation, we also desire that the extension of every spanning interval have a unique representation. There are a number of situations where two different spanning intervals will have the same extension. First, all spanning intervals tex2html_wrap_inline9504 where tex2html_wrap_inline9536 , tex2html_wrap_inline9538 , tex2html_wrap_inline9540 , or tex2html_wrap_inline9542 represent the empty set of intervals, because there are no intervals with an endpoint that is less than or equal to minus infinity or greater than or equal to infinity. Second, if tex2html_wrap_inline9544 , tex2html_wrap_inline9546 , tex2html_wrap_inline9548 , or tex2html_wrap_inline9550 , the value of  tex2html_wrap_inline9136 , tex2html_wrap_inline9138 , tex2html_wrap_inline9140 , or  tex2html_wrap_inline9142 does not affect the denotation respectively, because there are no intervals with infinite endpoints. Third, if j>l, j can be decreased as far as l without changing the denotation, because all intervals where the upper endpoint is less than the lower endpoint equivalently denote the empty interval. Similarly, if k<i, k can be increased as far as i without changing the denotation. Fourth, all spanning intervals where i>j or k>l represent the empty set of intervals, because the range of possible endpoints would be empty. Fifth, all spanning intervals where i=j and either  tex2html_wrap_inline9136 or  tex2html_wrap_inline9138 is false (indicating an open range for the lower endpoint) represent the empty set of intervals, because the range of possible endpoints would be empty. Similarly, all spanning intervals where k=l and either  tex2html_wrap_inline9140 or  tex2html_wrap_inline9142 is false (indicating an open range for the upper endpoint) also represent the empty set of intervals. Sixth, all spanning intervals where i=l and either  tex2html_wrap_inline9128 or  tex2html_wrap_inline9130 is false (indicating an open interval) also represent the empty set of intervals, because the endpoints of an open interval must be different. Seventh, if j=l and  tex2html_wrap_inline9142 is false, the value of  tex2html_wrap_inline9138 does not affect the denotation, because if j=l and  tex2html_wrap_inline9142 is false, the upper endpoint must be less than l and the lower endpoint must be less than or equal to j which equals l, so the lower endpoint must be less than j. Similarly, if k=i and  tex2html_wrap_inline9136 is false, the value of  tex2html_wrap_inline9140 does not affect the denotation. Eighth, if j=l and either  tex2html_wrap_inline9128 or  tex2html_wrap_inline9130 is false, the value of  tex2html_wrap_inline9138 does not affect the denotation, because the lower endpoint of an open interval must be less than its upper endpoint. Similarly, if k=i and either  tex2html_wrap_inline9128 or  tex2html_wrap_inline9130 is false, the value of  tex2html_wrap_inline9140 does not affect the denotation.

To create a situation where the extension of every spanning interval has a unique representation, let us represent all empty sets of intervals as  tex2html_wrap_inline9386 . When the values of i, j, k, l, tex2html_wrap_inline9128 , tex2html_wrap_inline9130 , tex2html_wrap_inline9136 , tex2html_wrap_inline9138 , tex2html_wrap_inline9140 , or  tex2html_wrap_inline9142 can be changed without changing the denotation, we will select the tightest such values. In other words, false values for the Boolean parameters, maximal values for the lower bounds, and minimal values for the upper bounds. Thus whenever we represent a spanning interval tex2html_wrap_inline9504 explicitly, it will have a nonempty extension and will satisfy the following normalization criterion:

displaymath1521

Criteria (1) through (8) correspond to points one through eight above.

A spanning interval tex2html_wrap_inline9504 is normalized if i, j, k, l, tex2html_wrap_inline9128 , tex2html_wrap_inline9130 , tex2html_wrap_inline9136 , tex2html_wrap_inline9138 , tex2html_wrap_inline9140 , and  tex2html_wrap_inline9142 cannot be changed without changing its denotation. Given a (potentially non-normalized) spanning interval  tex2html_wrap_inline8292 , its normalization tex2html_wrap_inline9682 is the smallest set of normalized spanning intervals that represents the extension of  tex2html_wrap_inline8292 . One can compute tex2html_wrap_inline9682 as follows:

displaymath1540

An important property of spanning intervals is that for any spanning interval  tex2html_wrap_inline8292 , tex2html_wrap_inline9682 contains at most one normalized spanning interval.gif


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

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