(b)(a)IxxyIyxyxyrIy2y > 1 /(x-5) 2y> (x-5)2y< 4 - (x-6)xyR2y< 4 - (x-6)Ix Ix (1)(2)

Figure 1: Figure (a) illustrates a binary relation Rxy given intensionally by the two inequalities y > (x ? 5)2 and y < 4 ? (x ? 6)2. Rxy determines the region rxy and is both y- and x-convex: the projection of rxy respectively over the x and y axes yields single bounded intervals (resp. Ix and Iy). In Figure (b), the relation Rxy is given intensionally by the constraints y > 1=(x ? 5)2

and y < 4 ? (x ? 6)2. In this last case, the relation is only y-convex since its projection over the x axis yields two distinct intervals Ix1 and Ix2.

In the following, a continuous CSP (CCSP),(P = (V; D; R)), is defined as a set V of variables x1; x2; : : : xn, taking their values respectively in a set D of continuous domains D1; D2; : : : ; Dn and constrained by a set of relations R1; : : : ; Rm. A domain is an interval of R. A relation is defined intensionally by a set of algebraic equalities and inequalities (see figure 1). A relation Rij is a total constraint: it takes into account the whole set of algebraic constraints involving the variables i and j. Each variable has a label defining the set of possible consistent values. The label Lx of a variable x is represented as a set of intervals fIx;1 = [xmin;1 : : : xmax;1]; : : :g.

2 Constraint and Label Representation

Constraints on continuous variables are most naturally represented by algebraic or transcendental equations and inequalities. However, as Faltings [5] has shown, this leads to incomplete local propagation when there are several simultaneous constraints between the same variables. More importantly, making a network path-consistent requires computing the intersection and union of constraints, operations which cannot be performed on (in)equalities. It is therefore necessary to explicitly represent and manipulate the sets of feasible value combinations.

Providing each variable with an interval label implicitly represents feasible regions by enclosing rectangles or hypercubes. As shown in Figure 2, this is not powerful enough for region intersection operations. To define a more precise and yet efficient representation, we observe that most applications satisfy the following two assumptions:

ffl each variable takes its values in a bounded domain (bounded interval)

ffl there often exists a maximum precision with which results can be used.

Provided that these two assumptions are verified, a relation Rx1:::xk can be approximated by carrying out a hierarchical binary decomposition of its solution space into 2k-trees (quadtrees for binary relations,octrees for ternary ones etc: : : )(see Figure 3). A similar representation