How to take into account piecewise constraints in constraint satisfaction problems

A particular data structure named a Quad Tree allows a better representation of solution space of binary continuous constraints C(x1,x2)C(x1,x2), than classical continuous consistencies. The generation and integration of this data structure do not raise any particular problem for continuous constraints defined by only one mathematical formula [Sam, D., 1995. Constraint consistency techniques for continuous domains. Ph.D. Thesis, École Polytechnique Fédérale de Lausanne]. In this paper, we propose to extend the method of generating Quad Trees in order to take into account, in CSPs, binary continuous constraints defined by a piecewise constraint, i.e. a set of functions defined on intervals. The first section presents the industrial requirements which led us to take into account this type of constraint in CSP. The second section recalls the principles of the Quad Tree. The last section describes our contributions relevant to Quad Tree extensions dealing with piecewise constraints.