Checking whether a line segment is above another in $\mathbb{R}^3$

Question

There are two non parallel line segments $U$ and $V$ in $\mathbb{R}^3$, each given by their two end points $u_0, u_1$ and $v_0, v_1$, such that if they are projected into $\mathbb{R}^2$ by their $x$ and $y$ coordinates, they intersect. We want to know whether the line $U$ is above $V$. More exactly, suppose their projections on $\mathbb{R}^2$ intersects at point $(x, y)$. We want to know whether the $z$ coordinates of line segment $U$ at point $(x, y)$ is larger than the $z$ coordinates of line segment $V$ at point $(x, y)$.

Assuming that $u_0, u_1, v_0, v_1$ are all lattice points, is there a way to do this that doesn't explicitly calculates the $x$, $y$ and $z$ coordinates? In order words, how to check this without floating point arithmetic?

Motivation

This comes up when I am trying to compute the 3D convex hull of the projection of a triangulation of polygon from $\mathbb{R}^2$ into $\mathbb{R}^3$ during the computation of the weighted delaunay triangulation of the set of points.

Answer 1

I think this condition does the job: $$ 0 \le \det\left[\begin{matrix} v_0-u_0 & u_1-u_0 & v_1-v_0 \end{matrix}\right] \det\left[\begin{matrix} P(u_1-u_0) & P(v_1-v_0) \end{matrix}\right] \tag{$\ast$} $$ Here $P$ is the coordinate projection onto the $xy$-plane; the matrix $\left[\begin{matrix} a & b \end{matrix}\right]$ means the matrix with vectors $a$ and $b$ as columns; the first determinant is $3\times3$ and the second is $2\times 2$. (Note that the latter determinant is a subdeterminant of the former, so there's some opportunity to reuse computational results.)

To derive this, consider the following method of solving the problem directly by computing $x,y,z$. First we find the intersection of the projections by solving the system $$ P(u_0) + s(P(u_1)-P(u_0)) = P(v_0) + t(P(v_1)-P(v_0)) \tag1 $$ Then we compute the $z$ coordinates and compare them: $$ u_{0z} + s(u_{1z}-u_{0z}) \mathrel{\stackrel{?}{\le}} v_{0z} + t(v_{1z}-v_{0z}) \tag2 $$ If you solve the system (1) using Cramer's rule and plug the resulting $s$ and $t$ into (2), you'll find that it's equivalent to ($\ast$)... assuming I haven't made some elementary error.

(Geometrically, ($\ast$) is checking the handedness of the tetrahedron formed by the four vertices.)