Introduction

In this paper we exhibit an interesting case where solving a set of
order of magnitude comparisons is demonstrably much faster than
solving the analogous set of simple order comparisons.
Specifically, given a set of constraints of the
form ``Points *a* and *b* are much closer together than points *c* and *d*,''
the consistency of such a set can be determined in low-order polynomial time.
By contrast, it is easily shown that solving a set of constraints of the form
``The distance from *a* to *b* is less than or equal to the distance
from *c* to *d*'' in one dimension is NP-complete, and in higher dimensions
is as hard as solving an arbitrary set of algebraic constraints over the reals.

In particular, the paper presents the following results:

- 1.
- The algorithm ``solve_constraints(S)'' solves a
system of constraints of the form ``Points
*a*and*b*are infinitely closer than points*c*and*d*'' in polynomial time (Section 5). - 2.
- An improved version of the algorithm runs in time
*O*(max(*n*^{2}*a*(*n*)),*ne*,*s*) where*n*is the number of variables,*a*(*n*) is the inverse Ackermann's function,*e*is the number of edges mentioned in the constraint set, and*s*is the size of the constraint set. (Section 6.1). - 3.
- An extended version of the algorithm allows the inclusion
of non-strict constraints of the form ``Points
*a*and*b*are not infinitely further apart than points*c*and*d*.'' The running time for this modified algorithm is slower than that of solve_constraints, but still polynomial time. (Section 6.2) - 4.
- A different extension of the algorithm allows the combination
of order of magnitude constraints on distances with
order comparisons on the points of the form ``Point
*a*precedes point*b*.'' (Section 6.3) - 5.
- The same algorithm can be applied to constraints
of the form ``The distance from
*a*to*b*is less than 1/*B*times the distance from*c*to*d*,'' where*B*is a given finite value, as long as*B*is greater than the number of variables in the constraint set. (Section 7) - 6.
- The first-order theory over such constraints is decidable. (Section 8)

As preliminary steps, we begin with a small example and an informal
discussion (section 2). We then give a formal account of
order-of-magnitude spaces (section 3)
and present a data structure called a *cluster tree*, which
expresses order-of-magnitude distance comparisons (section 4).
We conclude the paper with a discussion of the significance of these
results (section 9).