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

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):

• How does one know in advance that the origin will end up inside the bounded region formed by the four lines? Sep 5, 2022 at 6:52
• Because S is defined by $\{(x,y): \bigwedge a_ix+b_iy-1<0\}$, since a_i0+b_i0-1=-1<0, (0,0) $\in$ S definitely. What we want is to find under which conditions S is closed. Sep 5, 2022 at 7:16
• Here are 4 lines: $x-y-1=5x-2y-1=3x+4y-1=2x+3y-1=0$. They do form an $S$, which is closed. But, the origin $\left(0,0\right)$ lies outside of $S$.
– YNK
Sep 5, 2022 at 8:25
• @Pat_Guangtailang From your comments, and your response to YNK, it appears you are not simply asking for a criterion so that four lines form a bounded region. Instead your set-up already guarantees that, if the four lines happen to form a bounded region, then that region will contain the origin. In a way you deal not with lines, but with specific half-planes determined by those lines. And your halfplanes are chosen to each contain the origin. Is this a fair summary? Sep 5, 2022 at 8:41
• @coffeemath I think so. Yes, the S of interest is in fact the intersection of 4 half planes generated by 4 lines, and the half plane is chosen to contain the origin. I have modified the problem description to avoid confusion. Sep 5, 2022 at 9:01

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$$.

• Do you mean that To guarantee S is enclosed, we just need to make sure the origin $(0,0)$ is in the quadrilateral whose four vertices are $(a_i, b_i), i=1,...,4$ respectively? Sep 8, 2022 at 1:52

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.

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.

• Interesting perspective. But there are at most 6 intersections, not exactly 6. For example, if $(a_ib_j - a_jb_i) = 0$ then there is no such intersection $V_{i,j}$. Then how could I derive constraints like (1), (2)? Sep 8, 2022 at 0:08
• My formulation is that: First, make sure there are at least 4 intersections; Second, if there is an intersection between two lines like $i, j$, then formulate a paired constraint like (1), (2), and then to guarantee S exists, we state that at least 4 of all the paired constraints must be satisfied. Sep 8, 2022 at 1:26
• Also, there can be three lines intersect at a common point, while there are still 4 intersections in total. It seems this scenario doesn't apply to your paired constraint like (1)(2). Sep 8, 2022 at 23:07
• And, can we extend the formulation to any n-sided polygon? For example, for a 5-sided polygon, we consider 5 vertices, each vertex and the origin must lie on the same side of the other 3 lines simultaneously? Sep 14, 2022 at 22:43
• It's like a typo 𝑉𝑗𝑛, since in Fig.1, 𝑉𝑗𝑛 and (0,0) are not in the same side of line i and line m, but you apply the constraints to vertex 𝑉𝑗𝑛. And I don't think you can multiply $a_ib_j - b_ia_j$ on both side of the inequality because $a_ib_j - b_ia_j$ may < 0. Sep 15, 2022 at 2:25

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):

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

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).