[ 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

Response by Vladik Kreinovich:

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

If I understand you correctly, you mean that:

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:

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?

[ 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

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 : Graphical counter