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 where , , , or 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 , , , or , the value of  , , , or  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  or  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  or  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  or  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  is false, the value of  does not affect the denotation, because if j=l and  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  is false, the value of  does not affect the denotation. Eighth, if j=l and either  or  is false, the value of  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  or  is false, the value of  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  . When the values of i, j, k, l, , , , , , or  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 explicitly, it will have a nonempty extension and will satisfy the following normalization criterion:

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

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

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

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

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