302 Chapter 13 Time for Planning
It can be shown that a constraint r is convex iff for every i and j such that [jri]
the zone defined by j with respect to i is a convex zone in the plane.
As mentioned earlier, IA
c
is the subset of the interval algebra restricted to
convex constraints. Out of the 2
13
constraints in IA, just 82 constraints are convex.
IA
c
is closed under the composition and intersection operations. Furthermore,
checking the consistency of an IA
c
network is a problem of polynomial complex-
ity for which the path-consistency algorithm is complete and provides minimal
networks.
A similar notion of convexity has been defined for PA. A constraint r in PA is said
to be convex iff the set of points t that meet [trt
0
], for t
0
fixed, is a convex part ...