Upside-Down

Let us assume the given vertices of the tetrahedron are $A( Ax, Ay, Az)$, $B( Bx, By, Bz)$, $C(Cx,Cy, Cz)$, and $D(Dx, Dy, Dz)$. According to the given constraints, $Az = Bz = Cz$. Let us assume $Az = Bz = Cz= d$. Since the origin is the center of mass, therefore $Az+Bz+Cz+Dz = 0$. It is trivial to show from this that $Dz = -3d$.

Now, for a given value of $k$, the following transformations will take place:

• Mirroring the tetrahedron with respect to the $XY$ plane: $A$ becomes $A’(Ax, Ay, -d)$, $B( Bx, By, -d)$, $C(Cx,Cy, -d)$, $D(Dx,Dy,3d)$.

• After mirroring, multiply each coordinate with a factor. The vertices become: $A’(kAx, kAy, -kd)$, $B’( kBx, kBy, -kd)$, $C’(kCx,kCy, -kd)$ and $D’(kDx,kDy,3kd)$.

• After the translation operation, $D’$ needs to have a $Z$ co-ordinate of $d$. Therefore, the translation along positive z-axis direction applied to each point would be $d-3kd$. After applying this translation to all the points, the coordinate of vertices becomes: $A’(kAx, kAy, d-2kd)$, $B’( kBx, kBy, d-2kd)$, $C’(kCx,kCy, d-2kd)$ and $D’(kDx,kDy,d)$.

Now, we need to check if tetrahedron $A’B’C’D’$ fits inside tetrahedron $ABCD$ or not. The tetrahedron $A’B’C’D’$ fits inside $ABCD$ if and only if points $A’$, $B’$, $C’$ and $D’$ all are situated on the inside of tetrahedron $ABCD$.

Now, how can we test if a point P is inside a tetrahedron $ABCD$? An $O(1)$ approach would be to notice that if point $P$ is inside tetrahedron $ABCD$, then the following equation holds.

Volume( tetrahedron $ABCD$) = Volume( tetrahedron $PBCD$)+Volume( tetrahedron $APCD$) +Volume( tetrahedron $ABPD$) +Volume( tetrahedron $ABCP$).

The following equation can be used for calculating the volume:

$Volume(ABCD) = \begin{vmatrix}A_x & A_y & A_z & 1\\B_x & B_y & B_z & 1\\C_x & C_y & C_z & 1\\D_x & D_y & D_z & 1\end{vmatrix}$

Now we have a technique to verify if for a specific value of k, the transformed tetrahedron ($T’$) fits inside the original tetrahedron ($T$) or not. To find the maximum value of $k$ for which $T’$ fits perfectly inside $T$, notice that by making $k$ bigger or smaller, we can define how big or how small $T’$ is. Also notice that if a transformed tetrahedron fits inside $T$, then scaled-down versions of that tetrahedron will also fit inside $T$. Therefore, we could run a binary search on $k$ from the values $0$ to $1$ and find the biggest value of $k$ for which $T’$ fits inside $T$.

Testing if $T’$ fits inside $T$ for a specific value of $k$ is $O(1)$. The binary search can either be terminated when the high and low values are sufficiently close.