# Internal tangent intersection of two point sets in linear time

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.

• Your link is unreachable. Your "definition by picture" is not clear enough for me. Do you have a more formal definition? – Yuval Filmus Jan 7 '17 at 16:14
• Can you define "internal tangent"? Is it guaranteed that there are always exactly two of them? Assuming the points on the convex hulls are sorted, can we traverse them via a "two-pointer" algorithm? e.g., one pointer $p$ advances clockwise around convex hull A, the other pointer $q$ advances counterclockwise around convex hull B to make the line $pq$ be the best candidate for an internal tangent possible given $p$, or something like that? – D.W. Jan 7 '17 at 16:52
• @YuvalFilmus sorry, the link should be fixed now. I'll try to give some more formal information, but unfortunately the paper is about as vague as I am, which is why I'm stuck. – phg Jan 8 '17 at 10:12
• @D.W. You mean like the tangent finding step of Mergehull? I thought about that, but here I don't have a cyclic order on the convex hull points -- I think computing that would increase the time to $\mathcal{O}(n \log n)$ again, wouldn't it? Also, I'm not even sure the tangents themselves need to be constructed explicitely, since only their intersection is of interest. – phg Jan 8 '17 at 10:27
• Yup, that would make my suggestion $O(n \log n)$ at best. If you really want $O(n)$ rather than $O(n \log n)$, forget my suggestion. – D.W. Jan 8 '17 at 17:23

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.