Set inversion
In mathematics, set inversion is the problem of characterizing the preimage X of a set Y by a function f, i.e., X = f−1(Y) = {x ∈ Rn | f(x) ∈ Y}. It can also be viewed as the problem of describing the solution set of the quantified constraint "∃ y . [f(x)=y ∧ Y(y)]", where Y(y) is a constraint, for example, an inequality, describing the set Y.
In most applications, f is a function from Rn to Rp and the set Y is a box of Rp (i.e. a Cartesian product of p intervals of R).
When f is nonlinear the set inversion problem can be solved using interval analysis combined with a branch-and-bound algorithm.
The main idea consists in building a paving of Rp made with non-overlapping boxes. For each box [x], we perform the following tests:
To check the two first tests, we need an interval extension (or an inclusion function) [f] for f. Classified boxes are stored into subpavings, i.e., union of non overlapping boxes. The algorithm can be made more efficient by replacing the inclusion tests by contractors.
The set X = f−1([4,9]) where f(x1, x2) = x12 + x22 is represented on the figure. For instance, since [-2,1]2+[4,5]2=[0,4]+[16,25]=[16,29] does not intersect the interval [4,9], we conclude that the box [-2,1]×[4,5] is outside X. Since [-1,1]2+[2,√5]2=[0,1]+[4,5]=[4,6] is inside [4,9], we conclude that the whole box [-1,1]×[2,√5] is inside X.
Set inversion is mainly used for path planning, for nonlinear parameter set estimation , for localization or for the characterization of stability domains of linear dynamical systems. .
...
Wikipedia