[ Marquette | MSCS | Corliss | Vladik's Intervals ]
Interval FAQ: [ Entry page | Contents | Search ]
About Sun's f95 with Interval Support

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

From Haitao Huang (h.haitao@ic.ac.uk), IC UK:

## How does one compare intervals?

I am a new-comer to interval arithmetic. Suppose there are two interval variables X1 and X2. I want to make a logical comparison to know if X1 is in X2, or there is some kind of overlapping. Is there any algorithm or library for this operation?

Haitao Huang

### Response by R. Baker Kearfott:

(rbk@usl.edu), University of Southwestern Louisianna:

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

(vladik@cs.utep.edu), Department of Computer Science, University of Texas at El Paso:

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).
Both relations can be expressed in terms of simple inequalities between the intervals' endpoints, so both checks can be done easily by comparing the endpoints of the intervals X1 and X2:
• 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.

### Response by Bill Older:

(wolder@nortelnetworks.com):

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?

[ Marquette | MSCS | Corliss | Vladik's Intervals ]
Interval FAQ: [ Entry page | Contents | Search ]
About Sun's f95 with Interval Support

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