2
$\begingroup$

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:

Internal tangent intersection

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.

$\endgroup$
  • 1
    $\begingroup$ Your link is unreachable. Your "definition by picture" is not clear enough for me. Do you have a more formal definition? $\endgroup$ – Yuval Filmus Jan 7 '17 at 16:14
  • $\begingroup$ 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? $\endgroup$ – D.W. Jan 7 '17 at 16:52
  • $\begingroup$ @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. $\endgroup$ – phipsgabler Jan 8 '17 at 10:12
  • $\begingroup$ @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. $\endgroup$ – phipsgabler Jan 8 '17 at 10:27
  • $\begingroup$ 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. $\endgroup$ – D.W. Jan 8 '17 at 17:23
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.