two variables quadratic inequalities solution

Question

Suppose there are $n$ quadratic inequalities, the form is $A_i x^2 + B_i y^2 + C_i xy + D_i x + E_i y + F_i \leq 0$, $(\forall i \in [1,n])$, where $x,y$ are two variables and $(A_i, B_i, C_i, D_i, E_i, F_i)$ are constant numbers, and all the range is $[-\infty,+\infty]$. So is there a simple way to find the solutions of these quadratic inequalities?

Answer 1

Have a look at the picture below (done using Geogebra with the "invert into a circle" tool). You see a branch of a hyperbola having $O(0,0)$ as one of its foci. Points $C,D,...Z$ are taken on it. The inverse of these points on this hyperbolic branch are points $C',D',... Z'$. How are these points obtained ? By the following transformation rule ; let us call $M$ the generic point on the hyperbola; the rule(s) for obtaining its image $M'$ by the given inversion is :

$R_1$ : $M'$ is aligned with $O$ and $M.$

$R_2$ : The product of distances $OM.OM'=1$.

These two rules can be summarized into a single one :

$\tag{1}\vec{OM'}=\frac{\vec{OM}}{\|\vec{OM} \|^2}$

A kind of miracle occurs : points $M'$ are all situated on an arc of ellipse, called the inverse of the hyperbolic arc. Of course, this is not a "miracle", it can be proved in a rather simple way. See remark below.

Morevover, the inverse of the other hyperbolic branch is "inverted" into the remaining arc $C'Z'$ of the ellipse.

Besides, interior points of the hyperbola are "mapped onto" interior points of the corresponding ellipse.

Thus your problem is reduced to the intersection of interior of ellipses which is simpler because it is bounded objects. If your application can be "pixel-based", it should be not too much time consuming to test whether there are still pixels into the increasingly shrinking region...

Remark: the ellipse can be given an analytical expression knowing the analytical expression of the hyperbola. Here is how. Using rules $R_1$ and $R_2$ above, if the image of $M(x,y)$ is $M'(X,Y)$, the reverse is true ( $M'(X,Y)$ has $M(x,y)$ for its image) with (refer to $(1)$ above):

$$\tag{2}(a) \ \cases{X=\frac{x}{x^2+y^2}\\Y=\frac{y}{x^2+y^2}} \ \ \iff \ \ (b) \ \cases{x=\frac{X}{X^2+Y^2}\\y=\frac{Y}{X^2+Y^2}}$$

It suffices then to plug formulas $(2)(b)$ into the equation of the hyperbola in order to get the equation of a conic section, which should always be an ellipse in this case (it has to be checked, but I will stop here because it is 1:30 CET in the night).

Answer 2

Now that the question is actually to find a solution area for inequalities $|xp^*|-|xp_i| \leq C_i$, $(\forall i \in [1,n])$, where we can set $p^*$ as the origin, and $p_i (\forall i \in [1,n])$ are points in 2-dimensional plane, and $|\cdot|$ is the Elucidean distance of two points. Actually we already know that there is a solution (sorry about that I overlook this important information in the above question), but the solution point is not know. Thus for each inequality, $C_i \geq -|p^*p_i|$ holds. The reason is that if there is one $C_i < -|p^*p_i|$, we cannot find a point satisfy the inequality (due to the triangle inequality the difference of any two edges is larger than or equal to the third edge). The goal is to find whether there is only one solution or a set of solutions.

From the above discussion, we have that $C_i \geq -|p^* p_i|, (\forall i \in [i,n])$. We classify this condition in 3 situations: $[-|p^*p_i|,0)$, $[0,|p^*p_i|]$, and $(|p^*p_i|,+\infty)$. We first show when $C_i \in (|p^*p_i|,+\infty)$, the inequality $|xp^*|-|xp_i| \leq C_i$ will always satisfied (also due to triangle inequality). Then we can discuss the other two situations. When $C_i \in [0,|p^*p_i|]$, we can transform the inequality to the property of hyperbola, where we set the length of foci $\frac{|p^*p_i|}{2}$, where $p^*,p_i$ are two foci points, and the other parameter (denote $a$ in most cases) of as $\frac{C_i}{2}$. Then the solution area will be the side oriented to $p^*$ of the curve (there are 2 curves of hyperbola) that far from $p^*$ (this can be easily see by drawing a hyperbola). Similarly, when $C_i \in [-|p^*p_i|,0)$, the solution area will also be the side oriented to $p^*$, but the curve close to $p^*$.

(The below part is my intuition...) Since the solution area of each inequality is a continuous area, so the final solution area will also be one continuous area (either closed or open). And we can know that if $p_i (\forall i \in [1,n])$ distributed all over the plane in every direction (it's like to rotate a hyperbola in 360 degree with different shapes), the final solution area will be a colsed area enclosing $p^*$. In the extremely case, when all the $C_i = -|p^*p_i|$, the answer is exactly $p^*$. So if the already known solution is not $p^*$ (say $s^*$), then the solution set will be an continuous area that covered the $s^*$ and $p^*$. (Now I am not sure whether it is right and how to formalized proved this... I will appreciate it if you can help me to formalize this or give some suggestions that I should be carefully aware of. Thanks.)