Interval FAQ
Haitao Huang -- How does one compare intervals?

How does one compare intervals?

Haitao Huang

Response by R. Baker Kearfott:

There are various systems. In our Fortran 90 module INTERVAL_ARITHMETIC (and in our package GlobSol), and in most elementary treatments of interval arithmetic, you have the operations of "subset" and "disjoint".

Bill Walster et al at Sun Microsystems (Bill.Walster@Eng.Sun.COM) devised a richer set of operators to make various logical situations easier to implement. (See www.mscs.mu.edu/~globsol/walster-papers.html, link to Interval Arithmetic Specification, "Certainly" and "Possibly" operators.) These operators are available with the GNU f-77 interval-enhanced compiler (ask Prof. Mike Schulte at schulte@eecs.lehigh.edu).

In this system, X1 is "certainly equal" to X2 if X1 and X2 are the same point; X1 is "possibly equal" to X2 if X1 and X2 overlap; and X1 and X2 are equal as sets if they are the same intervals. (Similarly, you have "possibly not equal", "certainly not equal" and "not equal as sets", etc.)

Of course, in a home-grown implementation, if you are representing intervals using end points, you can compare the end points to get the answers you want. But I'd recommend one of the pre-written packages at this point, in Fortran, C, C++, Pascal, or Matlab. (See also Interval compilers and programming environments)

Baker Kearfott

Response by Vladik Kreinovich:

If I understand you correctly, you mean that:

• you have two intervals X1=[a1,b1] and X2=[a2,b2], and
• you want to check:
• whether X1 is a subset of X2, and
• whether X1 and X2 overlap (i.e., whether these two intervals have common elements).

• X1 is a subset of X2 if and only if a2 <= a1 and b1 <= b2
• the intervals X1 and X2 have a common element if and only if max(a1, a2) <= min(b1, b2), i.e., iff a1 <= b2 and a2 <= b1.

Vladik Kreinovich

Response by Bill Older:

This area was explored some in BNR Prolog's interval constraint system. In a functional interval package (where intervals are essentially just conventional data structures), a variety of such relations (Allen relations) can be defined of course. However, in the constraint framework the possibilities are very restricted because of the formal requirements of monotonciity and stability under narrowing etc.

The subinterval relation X <= Y is one which can be defined and is both interesting and useful. Its interval (2nd order) interpretation is that X is contained in Y, with the degenerate case of X element of Ywhen X is a point, and the doubly degenerate 1st order interpretation as equality. As a constraint, however, it acts as a "diode", propagating narrowing from Y to X and not from X to Y; it therefore plays a role similar in many ways to assignment operators in conventional programming languages. In particular, observational data can be gated through such a diode into an interval computation so that the computation cannot back-narrow the data. Similarly, the parameters of a parametrized computation can be isolated from the computations they control and so on.

The other two relations I recall that are constraint defineable are "ends together" =| and "starts together" |=. These allow -- if I remember correctly -- the relation of "overlaps" to be formulated as a constraint, from which follows the n-ary relation "connected/covers". Note that these examples are all different ways of splitting the equality relation, == is equiv. <= & => and also == is equiv. =| & |=.

Bill Older

See also What do X < Y and X > Y mean?

If you have a question related to validated computing, interval analysis, or related matters, I recommend

• Vladik Kreinovich's Interval Computation web site, or
• Submit it to the interval computations listserv: reliable_computing@interval.louisiana.edu

This page URL: http://www.mscs.mu.edu/~georgec/IFAQ/huang1.html
Last modified July 7, 1999. Send comments to (georgec@mscs.mu.edu)
Access count since 20 Apr 1999 :