I need the feasible region of polynomials:
$$x = x_0 + x_1 e_1 + \cdots + x_n e_n$$
$$y = y_0 + y_1 e_1 + \cdots + y_n e_n$$
with $e_i \in [-1, 1]$, for all $i \in \{1, ..., n\}$.
We are given $x_0, x_1, ..., x_n$ and $y_0, y_1, ..., y_n$, but all $e_i$ are unknown, and vary independently (think of them as noise symbols for each term - e.g. rounding errors). I want to know what $x$ and $y$ can equal if we independently perturb all $e_i$ symbols between $−1$ and $1$. Note that, for all $i \in \{1, ..., n\}$, $x_i e_i$ and $y_i e_i$ terms are correlated, because they both share the $e_i$ noise symbol. The context is affine arithmetic, if that helps at all.
Is this possible? I looked at a seemingly related method by the name of linear programming, but I cannot figure out how to formulate the problem properly when there are many bounded variables, as in the above equations.
I have a rather brute-force MATLAB algorithm that computes the convex hull of the equations, with all permutations of the bounded $e$ coefficients set to $-1$ and $1$, but it is useless when $n$ is large.
Many thanks.