Internal tangent intersection of two point sets in linear time
I found a way to solve the problem in my case -- maybe that only applies to the special conditions found in the paper. There, the two point sets can be assumed to be non-collinear and always separable by a line parallel to one of the coordinate axes, and we always know that $A$ is "left of" (or "above") $B$.

In this case, we can represent a line simply by $y = kx + d$, and get one internal tangent by minimizing the function $F(k, d) = k$ subject to
$$
\forall v \in A: v_y \leq k  v_x + d\\
\forall v \in B: v_y \geq k  v_x + d.
$$
The other one can  be found by swapping $A$ and $B$ (or the relations) and maximizing.