Ufyukyu

Question

The following is an old high school exercise:

Let $A = (5, 4, 6)$ and $B = (1,0,4)$ be two adjacent vertices of a cube in $mathbb{R}^3$. The vertex $C$ lies in the $xy$-plane.

a) Compute the coordinates of the other vertices of the cube such that all $x$- and $z$-coordinates are positive.

b) Let $$g: vec{r} = begin{pmatrix} 10\1\5 end{pmatrix} + lambda begin{pmatrix} 1\1\-1 end{pmatrix}$$
be a line. Compute the coordinates of the intersection points of $g$ and the cube.

Question: What is the most efficient way using high school level maths to compute the intersection points by hand?

The most obvious approach would be to intersect the line with all six planes containing the cube's faces. This requires me to solve six $3 times 3$ systems of linear equations which will probably take a while. Even worse, I will then have to check if the intersection points really belong to the surface of the cube. These are another six $3 times 2$ systems of linear equations. Of course, the first six systems of linear equations are much easier to compute using the coordinate form of the planes, but still it will take a while.

A maybe more elegant approach would be to translate and rotate the cube such that one vertex coincides with the origin and the edges lie on the (positive) coordinate axes. Apply the same translation and rotation to $g$ and the intersection points are much easier to compute. It is also much easier to check whether or not the resulting points lie on the surface of the cube. However, in general, the rotation matrix will be very messy and therefore not advisable to do by hand.

Is there a different approach that avoids a lot of (messy) computation? I feel like there has to be some geometric property I am missing which allows for a completely different approach. After all, this is meant to be solved by high schoolers by hand.

You maye have a look here or look for sites/books dedicated to computational geometry. By using vector dot and cross products, you can avoid solving linear systems (however, computationally it's similar). — Nov 22 '18 at 12:07

score 1 · Accepted Answer · 2018-11-29 14:57:44Z

Let $C(p,q,0)$. Since $AB^2=BC^2$ and $2AB^2=AC^2$, solving the system
$$6^2=(1-p)^2+(0-q)^2+(4-0)^2quadtext{and}quad 2times 6^2=(5-p)^2+(4-q)^2+(6-0)^2$$gives
$$(p,q)=(-1,4),(5,-2)$$

Let $D(r,s,t)$. Since the midpoint of the side $AC$ is the same as the midpoint of the side $BD$, we get
$$frac{5+p}{2}=frac{1+r}{2},qquad frac{4+q}{2}=frac{0+s}{2},qquad frac{6+0}{2}=frac{4+t}{2}$$
i.e.
$$r=p+4,qquad s=q+4,qquad t=2$$

Therefore, we have either $C(-1,4,0),D(3,8,2)$ or $C(5,-2,0),D(9,2,2)$.

Case 1 : $A(5,4,6),B(1,0,4),C(-1,4,0),D(3,8,2)$ which are on the plane $2x-y-2z+6=0$.

Solving $(2t)^2+(-t)^2+(-2t)^2=6^2$ gives $t=pm 2$.

For $t=2$, the other vertics are $A'(9,2,2),B'(5,-2,0),C'(3,2,-4),D'(7,6,-2)$.
Note here that if a point $(a,b,c)$ is either in or on the cube whose vertices are $P_i(X_i,Y_i,Z_i) (i=1,2,cdots, 8)$ , then
$$min(X_1,X_2,cdots, X_8)le ale max(X_1,X_2,cdots, X_8),$$
$$min(Y_1,Y_2,cdots, Y_8)le ble max(Y_1,Y_2,cdots, Y_8),$$
$$min(Z_1,Z_2,cdots, Z_8)le cle max(Z_1,Z_2,cdots, Z_8)$$
Solving the system of inequalities
$$-1le 10+lambdale 9quad text{and}quad -2le 1+lambdale 8quadtext{and}quad -4le 5-lambdale 6$$gives$$lambda=-1$$Then, however, $(9,0,6)$ is not on the cube since $A'(9,2,2)$ is the only vertex whose $x$-coordinate is $9$ which is the maximum of $x$.

For $t=-2$, the other vertices are $A'(1,6,10),B'(-3,2,8),C'(-5,6,4),D'(-1,10,6)$.
Then, however, there are no $lambda$ satisfying the system of inequalities $$-5le 10+lambdale 5quad text{and}quad 0le 1+lambdale 10quadtext{and}quad 0le 5-lambdale 10$$

Case 2 : $A(5,4,6),B(1,0,4),C(5,-2,0),D(9,2,2)$ which are on the plane $x-2y+2z-9=0$.

Solving $t^2+(-2t)^2+(2t)^2=6^2$ gives $t=pm 2$.

For $t=-2$, we get the same vertices as those in the case for $t=2$ in Case 1.
For $t=2$, the other vertices are $A'(7,0,10),B'(3,-4,8),C'(7,-6,4),D'(11,-2,6)$. Now, solving the system of inequalities
$$1le 10+lambdale 11quad text{and}quad -6le 1+lambdale 4quadtext{and}quad 0le 5-lambdale 10$$gives$$-5lelambdale 1tag1$$The four vertices $A',B',C',D'$ are on the plane $x-2y+2z-27=0$. Solving $(10+lambda)-2(1+lambda)+2(5-lambda)-27=0$ gives $lambda=-3$ which satisfies $(1)$ to have $P(7,-2,8)$ which is on the cube since $vec{A'P}=frac 13vec{A'B'}+frac 13vec{A'D'}$.

The four vertices $A,D,D',A'$ are on the plane $2x+2y+z-24=0$. Solving $2(10+lambda)+2(1+lambda)+(5-lambda)-24=0$ gives $lambda=-1$ which satisfies $(1)$ to have $Q(9,0,6)$ which is on the cube since $vec{AQ}=frac 23vec{AA'}+frac 23vec{AD}$.

Since three vectors $vec{AA'}=(2,-4,4),vec{AB}=(-4,-4,-2)$ and $vec{AD}=(4,-2,-4)$ are not parallel to $(1,1,-1)$, we see that the number of the intersection points of $g$ and the cube $ABCD$-$A'B'C'D'$ is at most $2$.

Therefore, the intersection points are $$color{red}{(7,-2,8)qquadtext{and}qquad (9,0,6)}$$

Added : I've just noticed that somehow I had skipped the question a). The condition in a) can make the solution above simpler avoiding separating it into cases.

The key point in the solution above is the inequality $(1)$. We can say that for $lambda$ which does not satisfy $(1)$, the point $(10+lambda,1+lambda,5-lambda)$ is not on the cube. Also, the number of the intersection points is at most $2$. Using these information, we could avoid a lot of computations even if you started to check the planes other than $A'B'C'D'$ and $ADD'A'$ on which the intersection points exist as follows :

$ABCD$ whose equation is $x-2y+2z-9=0$. Then, we get $lambda=3$ which does not satisfy $(1)$.

$BCC'B'$ whose equation is $2x+2y+z-6=0$. Then, we get $lambda=-7$ which does not satisfy $(1)$.

$CC'D'D$ whose equation is $2x-y-2z-12=0$. Then, we get $lambda=1$ to have $(11,2,4)$ which is not on the cube since $D'(11,-2,6)$ is the only vertex whose $x$-coordinate is $11$ which is the maximum of $x$.

$ABB'A'$ whose equation is $2x-y-2z+6=0$. Then, we get $lambda=-5$ to have $(5,-4,10)$ which is not on the cube since $A'(7,0,10)$ is the only vertex whose $z$-coordinate is $10$ which is the maximum of $z$.

Also, after knowing all the coordinates of the eight vertices, you don't need to solve a system of linear equations in order to find the equations of planes. For example, since $vec{AA'}=(2,-4,4)$, we see that the equation of the plane $A'B'C'D'$is of the form $x-2y+2z+k=0$. Substituting the coordinates of $A'$ gives $k=-27$.

score 0 · Accepted Answer · 2018-11-29 02:22:13Z

Let's assume you know the coordinates of the vertices $V_{ijk}$, $i, j, k in 0, 1$, so that the cube edge vectors are
$$begin{aligned}
vec{e}_i &= left [ begin{matrix} x_i \ y_i \ z_i end{matrix} right ] = overrightarrow{V_{000} V_{100}} = overrightarrow{V_{001} V_{101}} = overrightarrow{V_{100} V_{101}} = overrightarrow{V_{110} V_{111}} \
vec{e}_j &= left [ begin{matrix} x_j \ y_j \ z_j end{matrix} right ] = overrightarrow{V_{000} V_{010}} = overrightarrow{V_{001} V_{011}} = overrightarrow{V_{100} V_{110}} = overrightarrow{V_{101} V_{111}} \
vec{e}_k &= left [ begin{matrix} x_k \ y_k \ z_k end{matrix} right ] = overrightarrow{V_{000} V_{001}} = overrightarrow{V_{010} V_{011}} = overrightarrow{V_{100} V_{001}} = overrightarrow{V_{110} V_{111}} \
end{aligned}$$
and the cube is really a cube and not a parallelepiped,
$$bbox{vec{e}_i cdot vec{e}_i = vec{e}_j cdot vec{e}_j = vec{e}_k cdot vec{e}_k} , quad
bbox{vec{e}_i cdot vec{e}_j = vec{e}_i cdot vec{e}_k = vec{e}_j cdot vec{e}_k = 0}$$

Note that the cube edge length is $sqrt{(5-1)^2 + (4-0)^2 + (6-4)^2} = 6$.

Here is a table of the possibilities, using $B = V_{000}$ and $A = V_{100}$:
$$begin{array}{c|c|c|c}
C & vec{e}_i & vec{e}_j & vec{e}_k \
hline
V_{010} = (5,-2,0) & (4,4,2) & (4,-2,4) & (2,-4,4) \
V_{010} = (5,-2,0) & (4,4,2) & (4,-2,4) & (-2,4,-4) \
V_{010} = (-1,4,0) & (4,4,2) & (-2,4,-4) & (-4,2,4) \
V_{010} = (-1,4,0) & (4,4,2) & (-2,4,-4) & (4,-2,-4) \
V_{111} = left(frac{13 - 3sqrt{7}}{2}, frac{11 + 3sqrt{7}}{2}, 0right) &
(4,4,2) &
left(3-frac{sqrt{7}}{2}, -frac{3}{2}+sqrt{7}, -3-sqrt{7}right) &
left(-frac{3}{2}-sqrt{7}, 3+frac{sqrt{7}}{2}, -3+sqrt{7}right) \
V_{111} = left(frac{13 - 3sqrt{7}}{2}, frac{11 + 3sqrt{7}}{2}, 0right) &
(4,4,2) &
left(-frac{3}{2}-sqrt{7}, 3+frac{sqrt{7}}{2}, -3+sqrt{7}right) &
left(3-frac{sqrt{7}}{2}, -frac{3}{2}+sqrt{7}, -3-sqrt{7}right) \
V_{111} = left(frac{13 + 3sqrt{7}}{2}, frac{11 - 3sqrt{7}}{2}, 0right) &
(4,4,2) &
left(3+frac{sqrt{7}}{2}, -frac{3}{2}-sqrt{7}, -3+sqrt{7}right) &
left(-frac{3}{2}+sqrt{7}, 3-frac{sqrt{7}}{2}, -3-sqrt{7}right) \
V_{111} = left(frac{13 + 3sqrt{7}}{2}, frac{11 - 3sqrt{7}}{2}, 0right) &
(4,4,2) &
left(-frac{3}{2}+sqrt{7}, 3-frac{sqrt{7}}{2}, -3-sqrt{7}right) &
left(3+frac{sqrt{7}}{2}, -frac{3}{2}-sqrt{7}, -3+sqrt{7}right) \
end{array}$$
In the first four cases, $C$ is on the same face as $A$ and $B$, diagonally opposite to $A$. In the last four cases, $C$ is on the opposite face, diagonally opposite to $B$.

Out of all of these possible $C$, only the first one yields a cube with all $x$ coordinates positive, and $z$ coordinates nonnegative. (Third yields all $z$ coordinates nonnegative, and two last ones all $x$ coordinates positive.)

The most obvious approach would be to intersect the line with all six planes containing the cube's faces. This requires me to solve six 3×3 systems of linear equations which will probably take a while.

Yes, but not systems of linear equations, just linear equations.

If we define a plane by its normal vector $vec{n}$ and a point on the plane $vec{v}$, then point $vec{p}$ is on the plane if and only if
$$vec{n} cdot (vec{p} - vec{v}) = 0$$

If we use form $vec{p}(lambda) = vec{o} + lambdavec{d}$ as the vector-valued function for the line, the intersection occurs when
$$vec{n} cdot ( vec{o} + lambdavec{d} - vec{v}) = 0$$
This can be directly solved for $lambda$:
$$lambda = frac{vec{n} cdot (vec{v} - vec{o})}{vec{n} cdot vec{d}}$$
If $vec{n}cdotvec{d} = 0$, the line is parallel to the plane, and there is no intersection.

This means you need 6 multiplications, 1 division, 4 additions, and 3 subtractions per line-plane intersection.

The six planes of the cube have
$$begin{array}{r|c|c}
; & vec{n} & vec{v} \
hline
+i: & vec{e}_i & V_{001} \
-i: & -vec{e}_i & V_{000} \
+j: & vec{e}_j & V_{010} \
-j: & -vec{e}_j & V_{000} \
+k: & vec{e}_k & V_{100} \
-k: & -vec{e}_k & V_{000} \
end{array}$$
In total, I count 36 multiplications, 6 divisions, and 42 additions or subtractions.

To determine whether point $vec{p}$ is in the cube, you need to do up to six further calculations, although only their sign matters:
$$begin{aligned}
i_+ &= vec{e}_i cdot (vec{p} - V_{001}) \
i_- &= vec{e}_i cdot (V_{000} - vec{p}) \
j_+ &= vec{e}_j cdot (vec{p} - V_{010}) \
j_- &= vec{e}_j cdot (V_{000} - vec{p}) \
k_+ &= vec{e}_k cdot (vec{p} - V_{100}) \
k_- &= vec{e}_k cdot (V_{000} - vec{p}) \
end{aligned}$$
If any of them is positive, then point $vec{p}$ is outside the cube.

In the worst case, each test is up to 18 multiplications and 30 additions or subtractions.

Because there are six tests, up to 144 multiplications, 6 divisions, and up to 222 additions and subtractions are needed.

A maybe more elegant approach would be to translate and rotate the cube such that one vertex coincides with the origin and the edges lie on the (positive) coordinate axes.

For position vectors $vec{o}$ the transformation is $T_o(vec{o})$,
$$T_p(vec{o}) = mathbf{T} ( vec{o} - V_{000} ) = mathbf{T}vec{o} - mathbf{T}V_{000}$$
and direction vectors $vec{d}$ is is $T_d(vec{d})$,
$$T_d(vec{d}) = mathbf{T} vec{d}$$
The inverse of the transformation matrix $mathbf{T}$ is $mathbf{T}^{-1}$, formed by the three edge vectors,
$$bbox{mathbf{T}^{-1} = left [ begin{matrix}
vec{e}_i & vec{e}_j & vec{e}_k
end{matrix} right ] = left [ begin{matrix}
x_i & y_i & z_i \
x_j & y_j & z_j \
x_k & y_k & z_k \
end{matrix} right ]}$$
because the inverse rotation transforms an unit cube to the same orientation as the cube at hand (just without the translation by $V_{000}$ for an exact match).

The inverse of the above 3×3 matrix is obtained using Cramer's rule
$$mathbf{T} = frac{1}{D} left [ begin{matrix}
y_j z_k - y_k z_j & x_k z_j - x_j z_k & x_j y_k - x_k y_j \
y_k z_i - y_i z_k & x_i z_k - x_k z_i & x_k y_i - x_i y_k \
y_i z_j - y_j z_i & x_j z_i - x_i z_j & x_i y_j - x_j y_i \
end{matrix} right ]$$
where the right side is the adjugate matrix of $mathbf{T}^{-1}$, and $D = operatorname{Det} mathbf{T}^{-1}$,
$$D = x_i ( y_j z_k - z_j y_k ) - x_j ( y_i z_k - z_i y_k ) + x_k ( y_i z_j - z_i y_j )$$
However, this means that if we use
$$mathbf{M} = left [ begin{matrix}
y_j z_k - y_k z_j & x_k z_j - x_j z_k & x_j y_k - x_k y_j \
y_k z_i - y_i z_k & x_i z_k - x_k z_i & x_k y_i - x_i y_k \
y_i z_j - y_j z_i & x_j z_i - x_i z_j & x_i y_j - x_j y_i \
end{matrix} right ]$$
then the transformations are
$$T_o(vec{o}) = frac{1}{D}mathbf{M}vec{o} - frac{1}{D}mathbf{M}V_{000}$$
and
$$T_d(vec{d}) = frac{1}{D}mathbf{M}vec{d}$$
which means that there is no need to include the division in the matrix; we can just do three divisions as the final step in the matrix, and precalculate the vector constant $frac{1}{D}mathbf{M}V_{000}$.

Alternatively, the inverse matrix can be found by hand using Gaussian elimination.

Matrix $mathbf{M}$ calculation needs 18 multiplications and 9 subtractions. Constant $D$ needs 9 multiplications and 5 subtractions. The $frac{1}{D}mathbf{M}V_{000}$ vector constant needs 9 multiplications, 3 divisions, and 6 additions. For each vector transformation, you need 9 multiplications, 3 divisions, and 6 additions (plus 3 subtractions for the position vector constant).

In total, you need 54 multiplications, 9 divisions, and 35 additions or subtractions to obtain the transformed line in the unit-cube coordinate system.

To find the $lambda$ to each face, you need an additional subtraction and a division, and to check whether that point is within the unit cube, three multiplications and three additions. Since there are six faces, the total cost is roughly 72 multiplications, 15 divisions, and 59 additions or subtractions.

In this particular case, $D = -24$ and
$$bbox{mathbf{M} = left [ begin{matrix}
8 & -8 & -12 \
-24 & 12 & 24 \
20 & -8 & -24 end{matrix} right ]}, quad
bbox{mathbf{T} = frac{1}{D}mathbf{M} = left [ begin{matrix}
-frac{1}{3} & frac{1}{3} & frac{1}{2} \
1 & -frac{1}{2} & -1 \
-frac{5}{6} & frac{1}{3} & 1 \
end{matrix}right ]} , quad
bbox{mathbf{T}V_{000} = frac{1}{D}mathbf{M}V_{000} = left[ begin{matrix}
frac{5}{3} \
-3 \
frac{19}{6} \
end{matrix}right ]}$$
so it does look like the exercise was designed for the inverse matrix approach.

Is there a different approach that avoids a lot of (messy) computation?

It turns out the matrix approach isn't messy at all.

G CabG Cab 18k31237 · Accepted Answer · 2018-12-02 01:19:35Z

a) finding the edges and vertices

Given
$$
A = left( {5,4,6} right)quad B = left( {1,0,4} right)
$$
then
$$
overline {BA} = 6quad mathop {BA}limits^ to = left( {matrix{ 4 cr 4 cr 2 cr } } right)quad
{bf u} = {{mathop {BA}limits^ to } over {overline {BA} }}
={1 over 3} left( {matrix{ {2} cr {2} cr {1} cr } } right)
$$
considering the conditions on $C$, we shall have
$$
eqalign{
& C = left( {x,y,0} right);quad mathop {BC}limits^ to = left( {matrix{ {x - 1} cr y cr { - 4} cr } } right) cr
& left{ matrix{
overline {BC} ^{,2} = 36 = left( {x - 1} right)^{,2} + y^{,2} + 16 hfill cr
mathop {BA}limits^ to ; cdot ;mathop {BC}limits^ to = 0 = 4x + 4y - 12 hfill cr} right.quad Rightarrow cr
& Rightarrow quad left{ matrix{ y^{,2} - 2y - 8 = 0 hfill cr 3 - y = x hfill cr} right.quad
Rightarrow quad C = left( {5, - 2,0} right) cr}
$$

so
$$
mathop {BC}limits^ to = left( {matrix{ 4 cr { - 2} cr { - 4} cr } } right)quad {bf v}
= {{mathop {BC}limits^ to } over {overline {BC} }} = {1 over 3}left( {matrix{ 2 cr { - 1} cr { - 2} cr } } right)
$$

The unit vector along the third edge from $B$ will be
$$
{bf w} = {bf v}; times ;{bf u} = {1 over 3}left( {matrix{ 1 cr { - 2} cr 2 cr } } right)
$$
where the sign of the product is choosen to respect the condition
for positive $x$ and $z$ coordinates.

Having the three unit vectors, it is easy to compute all the points.
$D$ will be
$$
D = C + mathop {BA}limits^ to = left( {9,2,2} right)
$$
while the points in the upper face will be given by
$$
A' = A + 6{bf w} = left( {7,0,10} right)
$$
and similarly for the others.

b) finding the intersections with the cube

For a point $P=(x,y,z)$ to be inside the cube, the vector $vec {BP}$ shall have its coordinates
in the reference $(bf u,bf v,bf w)$ contemporaneously within the range $[0,6]$. That is
$$
left{ matrix{
0 le mathop {BP,}limits^ to cdot ;{bf u} le 6 hfill cr
0 le mathop {BP,}limits^ to cdot ;{bf v} le 6 hfill cr
0 le mathop {BP,}limits^ to cdot ;{bf w} le 6 hfill cr} right.
$$

The dot products are easily computed
$$
eqalign{
& mathop {BP}limits^ to = left( {matrix{ {10} cr 1 cr 5 cr
} } right) - left( {matrix{ 1 cr 0 cr 4 cr
} } right) + lambda left( {matrix{ 1 cr 1 cr { - 1} cr
} } right) = left( {matrix{ 9 cr 1 cr 1 cr
} } right) + lambda left( {matrix{ 1 cr 1 cr { - 1} cr
} } right) cr
& mathop {BP,}limits^ to cdot ;{bf u} = ,{1 over 3}left( {matrix{ 2 cr 2 cr 1 cr
} } right) cdot left( {left( {matrix{ 9 cr 1 cr 1 cr
} } right) + lambda left( {matrix{ 1 cr 1 cr { - 1} cr
} } right)} right) = 7 + lambda cr
& mathop {BP,}limits^ to cdot ;{bf v} = ,{1 over 3}left( {matrix{ 2 cr { - 1} cr { - 2} cr
} } right) cdot left( {left( {matrix{ 9 cr 1 cr 1 cr
} } right) + lambda left( {matrix{ 1 cr 1 cr { - 1} cr
} } right)} right) = 5 + lambda cr
& mathop {BP,}limits^ to cdot ;{bf w} = ,{1 over 3}left( {matrix{ 1 cr { - 2} cr 2 cr
} } right) cdot left( {left( {matrix{ 9 cr 1 cr 1 cr
} } right) + lambda left( {matrix{ 1 cr 1 cr { - 1} cr
} } right)} right) = 3 - lambda cr}
$$
and so is the system of inequalities
$$
left{ matrix{ 0 le 7 + lambda le 6 hfill cr 0 le 5 + lambda le 6 hfill cr 0 le 3 - lambda le 6 hfill cr} right.quad
Rightarrow quad left{ matrix{ - 7 le lambda le - 1 hfill cr - 5 le lambda le 1 hfill cr - 3 le lambda le 3 hfill cr} right.quad
Rightarrow quad - 3 le lambda le - 1
$$

For $lambda$ outside of the given range, the three inequalities are not satisfied contemporaneously: the point is not inside the cube.

Thus the limits of the range are the values of $lambda$ for which the line intersects the cube, and we have just to place them
in the equation of the line, to get
$$
P_{,1} = left( {matrix{ 10 cr 1 cr 5 cr
} } right) - 3left( {matrix{ 1 cr 1 cr { - 1} cr
} } right) = left( {matrix{ 7 cr { - 2} cr 8 cr
} } right)quad P_{,2} = left( {matrix{ 10 cr 1 cr 5 cr
} } right) - left( {matrix{ 1 cr 1 cr { - 1} cr
} } right) = left( {matrix{ 9 cr 0 cr 6 cr
} } right)
$$

As a rough check, note that
$$
mathop {BP_{,1} }limits^ to = left( {matrix{ 6 cr { - 2} cr 4 cr
} } right)quad mathop {BP_{,2} }limits^ to = left( {matrix{ 8 cr 0 cr 2 cr
} } right)
$$
which when expressed in the $(bf u, bf v, bf w)$ become
$$
mathop {BP_{,1} }limits^ to _{,left( {u,v,w} right)} = left( {matrix{ 4 cr 2 cr 6 cr
} } right)quad quad mathop {BP_{,2} }limits^ to _{;left( {u,v,w} right)} = left( {matrix{6 cr 42 cr 4 cr
} } right)
$$

score 1 · Accepted Answer · 2018-11-29 14:57:44Z