Triangle formed by straight lines

[PeroK]

Thanks very much for your input. I will try this problem again, this time with a better understanding!

The reason geometry is not allowed for this problem, is because this is not actually from a geometry class. This problem is from one of my modules on inequalities, sets and logic (to summarise).

I can't see how you could figure this out from sets and logic without having some geometric insight. I certainly could make no progress without a sketch. I think I understand the book's solution. We label the three lines $A, B, C$, then the vertices opposite these lines $V_A, V_B, V_C$.

Then, taking these in order: $V_A$ satifies the linear equations of lines $B$ and $C$ and we compute its value for the linear equation for line $A$. We can call this function $a$ or $a(x, y)$. We note whether its value is positive of negative. Then do the same for vertices $V_B$ and $V_C$. The pattern we get in this case is $+, -, -$. This is then the pattern we are looking for in the next step, which is to compute the three linear functions for the point in question. If we get the same pattern (in this case $+, -, -$) it's an interior point. Otherwise, it's outside the triangle.

Unless this has been covered by your course (?) I don't see how you could figure this out for yourself.

 

[PeroK]

It was said: "so there are 7 sign patterns that all define the exterior". In fact, the exterior of a triangle is described by 6 areas. Three are each adjacent to a side of the triangle; these are inside of two of the lines, but outside the third. Three are each adjacent to a vertex; these are inside of one of the lines, but outside the other two. What this means is that of the 8 possible sign patterns, 1 indicates the interior, 6 indicate the exterior, and 1 is forbidden. Which I find interesting. The forbidden area would be on the outside of all three lines, but this is geometrically impossible.

Neverthless, if we take my example:
$$a(x, y) = y, \ b(x, y) = x - y, \ c(x, y) = x + y - 1$$And consider the point $(2, 1)$, we find that:
$$a(2, 1) = 1, \ b(2, 1) = 1, \ c(2, 1) = 2$$And, impossible or not, we have the $+, +, +$ signature!

 

[Office_Shredder]

Neverthless, if we take my example:
$$a(x, y) = y, \ b(x, y) = x - y, \ c(x, y) = x + y - 1$$And consider the point $(2, 1)$, we find that:
$$a(2, 1) = 1, \ b(2, 1) = 1, \ c(2, 1) = 2$$And, impossible or not, we have the $+, +, +$ signature!

I think you're missing this conceptually. The impossible sign pattern for this, if I did the math right, is -,-,+. Because y<0 from the first one, the second one makes x<y<0, then the third one is the sum of three negative numbers so can't be positive.

 

[PeroK]

I think you're missing this conceptually. The impossible sign pattern for this, if I did the math right, is -,-,+. Because y<0 from the first one, the second one makes x<y<0, then the third one is the sum of three negative numbers so can't be positive.

There's an 8th forbidden gluon state as well!

https://en.wikipedia.org/wiki/Gluon#Eight_colors

 

[Office_Shredder]

I guess a neat fact, the impossible combination is sign flipped in every spot from the interior, which I guess is another way to figure out which one the interior is. It's not hard to deduce in the original problem that -,+,+ is the impossible combination.

 

[Frabjous]

I deleted my precious attempt. I think this algorithm will work. It ain’t pretty. It generalizes Perok’s approach.
1) Find the longest side of the triangle (one way is define normalized direction vectors for each line and then take inner products to find the largest angle)
2) Redefine the coordinate system so that the longest side of the triangle is on the new x-axis. Notice that the triangle is now above or below the new x-axis. Also since the longest side is on the axis, both of the angles opposite to the other two sides are acute.
4) Determine if the point is above or below the new x-axis.
5) If it above the new x-axis, it needs to be below the other two lines (in the new coordinate system). If it below the new x-axis, it needs to be above the other two lines (in the new coordinate system).

 

[Office_Shredder]

I deleted my precious attempt. I think this algorithm will work. It ain’t pretty. It generalizes Perok’s approach.
1) Find the longest side of the triangle (one way is define normalized direction vectors for each line and then take inner products to find the largest angle)
2) Redefine the coordinate system so that the longest side of the triangle is on the new x-axis. Notice that the triangle is now above or below the new x-axis. Also since the longest side is on the axis, both of the angles opposite to the other two sides are acute.
4) Determine if the point is above or below the new x-axis.
5) If it above the new x-axis, it needs to be below the other two lines (in the new coordinate system). If it below the new x-axis, it needs to be above the other two lines (in the new coordinate system).

But we agree this is significantly worse than the solution from the book right?

 

[Frabjous]

But we agree this is significantly worse than the solution from the book right?

Mine is a painful solution. With yours, I am unsure of how to setup the direction of the inequalities without drawing a figure which we were forbidden to do.

 

[PeroK]

Mine is a painful solution. With yours, I am unsure of how to setup the direction of the inequalities without drawing a figure which we were forbidden to do.

The idea with the vertices and seven regions can be made ultimately purely algebraic. My issue is how you arrive at that without drawing a sketch. Moreover, how exactly is the interior of a triangle defined if not from a sketch? Even if the sketch is a mental picture of the plane geometry involved.

Once you have things nailed down in 2-3 dimensions, you may have to trust to algebra when generalizing.

 

[Office_Shredder]

The idea with the vertices and seven regions can be made ultimately purely algebraic. My issue is how you arrive at that without drawing a sketch. Moreover, how exactly is the interior of a triangle defined if not from a sketch? Even if the sketch is a mental picture of the plane geometry involved.

Once you have things nailed down in 2-3 dimensions, you may have to trust to algebra when generalizing.

The interior of the triangle is the only bounded intersection of three half spaces defined by splitting the plane by the given equations.

Yes i agree if you are given this question without having worked with polygons before like this drawing a picture is a good way to gain some intuition. This is like complaining if someone asks a question about continuous functions that doesn't permit a picture as a proof - the whole point is to take your picture, and turn it into an actual math proof.

 

[Frabjous]

Mine is a painful solution. With yours, I am unsure of how to setup the direction of the inequalities without drawing a figure which we were forbidden to do.

I missed the book solution in post 15. It uses the vertices to determine the directions. I feel like an idiot obtuse.

 

[Office_Shredder]

I missed the book solution in post 15. It uses the vertices to determine the directions. I feel like an idiot.

There's a lot going on in this thread. I was genuinely checking that you agreed with the book solution, since it seems easy to miss it in the conversation.

 

[andrewkirk]

This diagram helps understand how the logic works but importantly you do not need it to do the calculation.

We define functions $f_1,f_2,f_3$ that assign a real number to each point on the plane, where for point $\mathbf v$, the value of $f_i(\mathbf v)=f_i((x,y))$ is that of the LHS of the $i$-th equation in the OP, where $x,y$ are the Cartesian coordinates of $\mathbf v$.

For each $i\in\{1,2,3\}$ and each $u\in\mathbb R$, the level set$$S_{i}(u):= \left\{ \mathbf v\in\mathbb R^2\ :\ f_i(\mathbf v) = u\right\}$$is a straight line. For a given $i$, all level sets are parallel. The value of $f_i((x,y))$ increases in a direction perpendicular to those lines, but we don't yet know which of the two perpendicular directions it is (eg NorthEast or SouthWest).

Define $b_i$ to be the constant on the RHS of the $i$-th equation in the OP. So we can write the $i$-th equation as:$$f_i((x,y)) = b_i$$The $i$-th equation is satisfied by the level set $S_{i}(b_i)$, ie the level set of $f_i$ on which $f_i$ gives value $b_i$. Let's call that level set for equation $i$ the $i$-th boundary line, because it will be a boundary of the triangle. On one side of that boundary line, $f_i$ will always give a value larger then $b_i$ and on the other side, always smaller.

For each $i$ we define $P_{i}$ to be the point of intersection for the two boundary lines that are not boundary line $i$. Now the entire triangle lies on one side of that boundary line, or on the line, and $P_i$ is in the triangle but not on that boundary line. So the weak inequality ($\geq$ or $\leq$) version of equation $i$ that applies to $P_i$ must also be satisfied by all points in the triangle.
That is, if $f_i(P_i)\leq b_i$ then $f_i(\mathbf v)\leq b_i$ for all points $\mathbf v$ in the triangle. And the same applies if we replace $\leq$ by $\geq$.

We test and find that:\begin{align*}
&f_1(P_1) = f_1((1.8, 0.8)) = 2\times 1.8+ 0.8 = 4.4\geq 2 = b_1\\
&f_2(P_2) = f_2((1,0)) = 2\times 1 + 3\times 0 = 2\leq 6 = b_2\\
&f_3(P_3) = f_3((0,2)) = 0 - 2 = -2 \leq 1 = b_3\\
\end{align*}For each $i$ the diagram shows as a dashed line the level set for $f_i$ that passes through point $P_i$.

So our triangle is defined as:$$\Delta\,P_1P_2P_3 = \left\{ \mathbf v\in\mathbb R^2\ :\
f_1(\mathbf v)\geq b_1\wedge f_2(\mathbf v)\geq b_2\wedge f_3(\mathbf v)\geq b_3\right\} $$where $\wedge$ means AND.

We can then test and see that $P$ satisfies this but $Q$ and $O$ (the origin) do not.

PS the book's solution in post 15 is just a very terse - and somewhat hard to follow - version of this approach.

PPS below is some python code to automate the solution, showing it's quite straightforward and requires no diagrams to determine directions:
[CODE lang="python" title="Python code"]
import numpy as np

# matrix of coefficients from equations (LHS)
M = np.array([[2, 1],\
[2, 3],\
[1, -1]])
# vector of constants from equations (RHS)
b = np.array([2, 6, 1])

# function to choose the 'other two' indices, given an index i in [0, 1, 2]
def not_i(i):
return np.where(i == 0, [1, 2], np.where(i == 1, [0, 2], [0, 1]))

# function to test whether the i-th linear function gives > or < b at point (x,y)
def test_val(x, y, i):
return np.sign(sum(M * np.array([x, y])) - b)

# set up v to be matrix of coordinates of the three triangle vertices
v = np.array([[0.0 ,0.0],\
[0.0, 0.0],\
[0.0, 0.0]] )
# set up vector 'signs' to give directions of the inequalities
signs = [1, 1, 1]
# loop to find the vertices (points of intersection) and directions of inequalities
for i in [0, 1, 2]:
v[i, :] = np.linalg.solve(M[not_i(i)], b[not_i(i)])
signs = test_val(v[i, 0], v[i, 1], i)

# using the above, define a function to test whether point (x, y) is in the triangle
def is_in_triangle(x, y):
is_in = True
for i in [0, 1, 2]:
is_in = is_in and (test_val(x, y, i) == signs)
return is_in

# apply the function to test each of the three points
print("Is (1, 1) in the triangle? ", is_in_triangle(1, 1)) # test point P
print("Is (1, 2) in the triangle? ", is_in_triangle(1, 2)) # test point Q
print("Is (0, 0) in the triangle? ", is_in_triangle(0, 0)) # test point O (origin)
[/CODE]
And here is the output:

Is (1, 1) in the triangle?  True
Is (1, 2) in the triangle?  False
Is (0, 0) in the triangle?  False

 

[Einstein44]

Thanks very much for everyones contribution! I think I got it now.