Internal tangent intersection of two point sets in linear time

Question

I need to find the intersection of the internal tangents of two point sets $V_a, V_b$ in $\mathbb{R}^2$, defined via their convex hulls. We can assume that the sets are disjoint and linearly separable, so I think the internal tangents are uniquely defined as the two lines which are tangent to each of the convex hulls of the sets, such that each set is on a different side. This is the point marked green here:

This paper ("Computing Plurality Points and Condorcet Points in Euclidean Space") I'm currently reading (paywalled, unfortunately...) says in a sort of side note that this problem can be solved using linear programming, in linear time in the number of points, but doesn't describe how.

For constructing a linear program, I thought about describing lines by $F(x, y) = ax + by + c= 0$, and optimizing a function of $a, b, c$. Then the obvious constraints would be $\forall v \in V_a: av_x + bv_y + c \geq 0$ and the according thing for $V_b$, to force the lines to go between the two sets.

But now I am stuck. For one, we need to constrain the space of lines somewhat; $\lVert (a, b) \rVert = 1$ would be natural to require, but that's not linear. Also, I'm not sure about the cost function; I thought about using

$$\min_{a,b,c} \sum_{v\in V_a} F(v_x, v_y) - \sum_{v\in V_b} F(v_x, v_y),$$

since $F$ is somehow a distance from the line (although not in the strict sense, I guess). But that is just guessing and also doesn't work -- I tried some things like I described in JuMP, but it always returned "infeasible".

How can this be formluated as a linear program? Alternatively, I can accept an algorithmic solution with linear time. Or a disproof, of course.

Answer 1

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.