Robin Hirsch, "From points to intervals", <I> Journal of
Applied Non-Classical Logics</I>, 1994, Vol. 4, No. 1, pp. 7--27. 
<P>

In traditional interval computations, an interval is defined as a pair
of numbers. In knowledge representation, we may define time interval
corresponding to an event as a pair of numbers if we are only
interested in the moments of time when the event started and ended;
but we can also add additional information: e.g.,
we can describe what exactly happens at each endpoint, what properties
of the situation hold at each of these moments of time, etc. 
<P>
In the paper under review, the author describes a general way to get
such generalized intervals from generalized "points" (i.e., numbers
with additional information). Namely, let a set of points be
already defined. This means that we have a set $S$ whose elements will
be called "points", and we have a set $\cal R$ of binary relations
$R(s,s')$ between points; we will called these relations <I> basic</I>.
We can then define <I> intervals</I> as pairs of points $(s^-,s^+)$,
$s^-\in S$, $s^+\in S$, and we can define {\it basic relations}
between intervals $(s^-,s^+)$ and $(t^-,t^+)$ as relations of the type
$R_1(s^-,t^-)\,\&\, R_2(s^-,t^+)\,\&\, R_3(s^+,t^-)\,\&\, R_4(s^+,t^+)$, where
$R_i$ are basic relations between points. 
<P>
In particular, if we take
$S=R$ and ${\cal R}=\{<,=,>\}$, we get Allen's interval algebra; if we
take $S=R$ and ${\cal R}$ consisting of the relations $s'-s\in [a,b]$
for different intervals $[a,b]$, we get a metric version of interval
algebra. 
<P>
We can apply the above-defined pairing operation to intervals teated
as "points", and get intervals of intervals (usually called <I>
twins</I> in interval computations). 
<P>
A natural question is: suppose that we know that for some finite set
of objects $x_1,\ldots,x_n$ (points or intervals), a set of relations
of the type $R_1(x_i,x_j)\vee ...\vee R_m(x_i,x_j)$ holds. Is this
knowledge consistent? 
<P>
Going from points to intervals can drastically increase the
computational complexity of this consistency-checking 
problem: for points with ordinal or
metric relations consistency can be checked by a cubic time algorithm;
for intervals, consistency problem is NP-hard even for ordering
relations only.