Formulate constraints such that the intersection area of 4 half planes (formed by 4 lines) is an enclosed convex quadrilateral containing origin

316 Views Asked by At

Background: There are four lines $A_ix + B_iy + C_i = 0 (A_i^2+B_i^2 \ne 0), i=1,...,4$, not passing through origin $(0,0)$, which means $C_i \ne 0, i = 1,...,4$. Without loss of generality, we assume $A_ix + B_iy + C_i | _{(0,0)} < 0, i=1,...,4$, namely $C_i < 0, i=1,...,4$. Thus, divided by $-C_i > 0$ on both sides of the line equation, we reduce the original line equation to $a_ix + b_iy - 1 = 0 (a_i^2+b_i^2 \ne 0), i=1,...,4$ where $a_i = A_i/(-C_i)$ and $b_i = B_i/(-C_i)$. We will use the reduced equation in this problem, and for convenience I formally write it as a theorem below:

Theorem: Any line not passing through the origin can be represented as $a_ix + b_iy - 1 = 0 (a_i^2+b_i^2 \ne 0)$ (namely, the set of all lines not passing through the origin = $\{ax+by-1=0: a,b \in \mathbb{R} \wedge a^2+b^2 \ne 0\}$ = $\{ax+by+c = 0: a,b,c \in \mathbb{R} \wedge a^2+b^2 \ne 0 \wedge c \ne 0\}$); Also, a line always cuts the whole plane into two half planes, and this representation ensures that any point in the same half plane as the origin $(0,0)$ always makes $a_ix + b_iy - 1 < 0$. We define the half plane of a line where the origin locates as the inner side, and the other half plane as the outer side of the line.

Problem: which constraints (on coefficients $a_i,b_i$) of the lines need to be formulated to guarantee that the area $S : = \{(x,y): \bigwedge a_ix + b_iy - 1 < 0(a_i^2+b_i^2 \ne 0), i = 1,...,4\}$ is a closed convex (the definition of $S$ guarantees if $S$ enclosed then it is convex) quadrilateral? (Of course, the origin is definitely inside $S$, by definition of $S$.)

A sketch is attached to illustrate this requirement (Here "close/open" just means “enclosed/not enclosed” or bounded/unbounded intuitively. Don't confuse it with the concept "closed/open set" in Topology): enter image description here

3

There are 3 best solutions below

8
On BEST ANSWER

ThreeLinesRWOI

In our attempt to gain better insight into the sought conditions that should be satisfied by a bundle of lines, none of which passes through the origin, we first study the case of three such lines (see $\mathrm{Fig.\space 1.}a$ and $\mathrm{Fig.\space 1.}b $). The lines are expressed as shown below in the format of the convention mentioned by OP. $$a_ix+b_iy-1= a_jx+b_jy-1= a_kx+b_ky-1=0$$

We know that each line divides the plane into two half-planes. $\mathrm{Fig.\space 1.}a$ lets us hypothesize that, if each of the three points of intersection (i.e. $V_{jk}$) and the origin lie in one of the half-planes generated by the line opposite to it (i.e. $L_i$), the three lines form a close region (i.e. triangle) which has the origin in its interior. $\mathrm{Fig.\space 1.}b$ confirms that this is in fact is the case, because one of the points of intersection, $V_{jk}$ to be precise, and the origin lie in the two different half-planes created by the line opposite to it (i.e. $L_i$).

With two slight adjustments, this supposition can be generalized to $n$ number of lines, none of which passes through the origin. Firstly, when there are $n$ lines at our disposal, we need to deal with $\dfrac{n\left(n-1\right)}{2}$ number of points of intersection. Secondly, each of these points must be checked against $\space n-2\space$ opposite lines. Last but not least, not all points of intersection need to satisfy all $n-2\space$ mandatory constrains they are subjected to. It is suffice to find $n$ all-obliging points, because we are here looking for an $n-$gon with origin in its interior.

FourLinesRWOI

Let us examine the case of four lines in detail. We expressed the lines as, $$a_ix+b_iy-1= a_jx+b_jy-1= a_mx+b_my-1= a_nx+b_ny-1=0$$

They have altogether six points of intersection between them (see $\mathrm{Fig.\space 2.}a$ and $\mathrm{Fig.\space 2.}b $) and some of them may lie at infinity. Each of them must satisfy two constrains.

If the point of intersection between first two lines is denoted by $V_{ij}$, then we have, $$V_{ij} = \left(-\dfrac{b_i-b_j}{a_1b_j-b_ia_j}, \dfrac{a_i-a_j}{a_1b_j-b_ia_j}\right).$$

Now we can test whether $V_{ij}$ and the origin lie on the same side of the other two lines, i.e. Line $m$ and Line $n$. Because inserting $x-$ and $y-$coordinates of points lying on the same half-plane of a line into its equation yields numerical values having the same sign, we have, $$ \dfrac{-a_m\left(b_i-b_j \right)+b_m\left(a_i-a_j\right)} {a_ib_j-b_ia_j}\lt 1 \qquad\text{and}\space\tag{1}$$ $$\dfrac{-a_n\left(b_i-b_j\right)+b_n\left(a_i-a_j\right)}{a_ib_j-b_ia_j}\lt 1.\qquad\qquad\tag{2}$$

If $V_{ij}$ satisfies both these inequalities, then it is definitely one of the four vertices of the quadrilateral demarcating the region $S$ , which accommodates the origin in its interior. In order to make sure that such region $S$ exists, we need to show that there are four such points of intersection, each satisfying a pair of inequalities similar to (1) and (2). Constrains for the other five points of intersection can be derived and tested in a procedurally similar manner.

The minimum number of points of intersection needed to be tested is four. On the other hand, the minimum number of points of intersection to be checked to show that there is no such region $S$ is three.

As shown in $\mathrm{Fig.\space 2.}a$, $V_{ij}$ and the origin $O$ are situated to the right of the line $n$. Both these pair of points are located below the line $m$ as well. Therefore, $V_{ij}$ satisfies both constrains. In contrast, the pair $V_{im}$ and the origin lie on the left half-plane of the line $j$ while located on the opposite half-planes of the line $n$. Therefore, $V_{im}$ fails to satisfy one constrain. In $\mathrm{Fig.\space 2.}b$, we see $V_{ij}$ violating both constrains, because it and the origin reside on opposite half-planes with respect to the lines $m$ and $n$.

There is a program written in VBA available for downloading at DropBox, which demonstrates the method describe above for testing whether four given lines can form a region (i.e. a convex quadrilateral) with origin in its interior. Since this program is written in a macro-enabled Excel work book, you must have MS Excel installed in your computer to run it.

1
On

Simply speaking, the four direction vectors of your lines $[a_i, b_i]^T$, when anchored at a common point, should not fit within any half plane whose edge passes through that point.

Anchor them at $O$ and you'll get that an open quadrilateral with vertices $(a_i, b_i)$ should contain $O$.

0
On

Some notes:

I don't think the answer provided by @CiaPan is right, some corrections are needed at least. Considering the following three examples, although all 4 normal vectors of 4 lines don't fit within any half plane, S formed by the 4 lines (the yellow colored area) is not an enclosed quadrilateral (it's a triangular area instead): enter image description here

For $n = 4$ different lines, all possible classifications of intersections are (according to the numbers and topology of intersections):

enter image description here

Further, we can consider all different scenarios where the origin and the set S (shadowed area) locate. For example, in Fig. 6 intersections, the origin may locate inside the convex quadrilateral or not.

Remarks:

  1. For n = 4 lines, there are at most 6 intersections, where $6 = C_n^2 = 1+2+ ... +(n-1) $

  2. The method of Induction is used to obtain all possible scenarios. First we consider all 2 possible scenarios for 2 lines, then add a new line to each of those 2 scenarios for 2 lines and obtain all 4 scenarios for 3 lines, and next we continue to add a new line to each of those 4 scenarios for 3 lines ...

  3. There is no possibility that there are 2 intersections for 4 lines, which can be proved through Proof by Contradiction.

  4. Having different numbers of intersections necessarily means different topology, but not conversely.

  5. Having at least 4 intersections is a necessary but not sufficient condition to form an enclosed convex quadrilateral; Forming an enclosed convex quadrilateral is also necessary but not sufficient to obtain $S$ that we want.

  6. There can be more than 1 closed quadrilateral. For example, for the scenario of 6 intersections, there is also a concave quadrilateral in addition to a convex quadrilateral. In fact, there are $6*5/2 = 15$ different combinations of four vertices.

  7. The representation of S can't ensure that S is enclosed, but if it is definitely enclosed then it must be a convex polygon (Be aware that S defined by 4 lines may be not a quadrilateral).