5
$\begingroup$

The problem: in 2d, given a line and an unordered set of $N$ points with real coordinates, find the intersection between the line and the convex hull of the points.

Clearly, one can explicitly construct the convex hull and find the answer in $O(N \log N)$. Is there a faster approach? Is there a superlinear lower bound on the complexity?

$\endgroup$

2 Answers 2

4
$\begingroup$

What you're asking for reduces to finding the so-called bridges of the convex hull across this line, i.e. the two edges of the convex hull which have one vertex on both sides of the line. Kirkpatrick and Seidel [1] show how to do this in linear time. Their method amounts to using the two dimensional linear programming algorithms independently discovered by Megiddo [2] and Dyer [3].

You can generalize this to any (constant) dimension. Let me illustrate it in 3D. We are given a set of $n$ points $S$ in euclidean $3$-space, a line $\ell$ and we want to compute the intersection of $\ell$ with the convex hull of $S$.

Without loss of generality, we can rotate everything and assume that $\ell$ is the line of equation $x=y=0$. We want to find the highest and lowest point (in terms of $z$ coordinate) of $\ell$ which is in the convex hull. To find the highest point, notice that this is the lowest point which is the intersection of $\ell$ with a plane $\pi$ which has all point of $S$ below or on it. Say the equation of $\pi$ is $z = ax +by + c$. The $z$-coordinate of the intersection of $\ell$ with $\pi$ is $c$. We thus want to minimize $c$ under the constraints that $z_i \leq ax_i +by_i + c$ for all $(x_i,y_i,z_i)\in S$. This can be modelled as a linear program in three variables ($a$,$b$ and $c$) and $n$ constraints. Using the linear time algorithm by Megiddo [4] it can be solved in $O(n)$ time if the number of variables is constant. Of course you can compute the lowest point of intersection similarly.

[1] David G. Kirkpatrick and Raimund Seidel. 1986. The ultimate planar convex hull algorithm? SIAM J. Comput. 15 (1986).

[2] Nimrod Megiddo, Linear time algorithm for linear programming in R3 and related problems, SIAM J. Comput. 12 (1983).

[3] Martin E. Dyer, Linear time algorithms for two- and three-variable linear programs, SIAM J. Comp. 13 (1984).

[4] Nimrod Megiddo, Linear programming in linear time when the dimension is fixed. J. ACM 31 (1984).

$\endgroup$
2
  • $\begingroup$ Nice. Do you have anything in mind for the same problem in higher dimensions? $\endgroup$
    – hidanom
    Jun 11 at 15:49
  • $\begingroup$ @hidanom I expanded my answer to include the claim for higher (but fixed) dimension. $\endgroup$
    – Tassle
    Jun 12 at 9:38
0
$\begingroup$

I think it can be done in O(N).

WLOG, we assume the line is $x=0$, and the intersection set is non empty. We can rotate the point set if the line is not $x=0$. The intersection check can be done in O(n) so we can make such assumption.

So we are going to find two point $(0,a)$ and $(0,b)$, such that $a$ is the maximum number and (0,a) is a point in the convex hull, and b is the minimum number.

Obviously, (0,a) must be on an edge of the convex hull.

Say the input point set is $S=\{ (x_1,y_1), \cdots, (x_n,y_n) \}$

We can get $S_1$ and $S_2$ in O(N) time.

$S_1 = \{ (x,y) | x\leq 0\} \cap S$ $S_2 = \{ (x,y) | x >0 \} \cap S$

if $S_2$ is empty then the intersection is an edge of the convex hull, we can get the intersection in O(N) time easily.

Otherwise. $(0,a)$ must be a point on the segment between a point $A\in S_1$ and a point $B\in S_2$

We can find the "highest" point in $S_1$ and $S_2$: the points with maximum y-coordinate. Let's say they are $P_1=(xx_1,yy_1)$ and $P_2=(xx_2,yy_2)$

If $yy_1 = yy_2$, then $(0,a)$ must be on the segment $P_1P_2$, i.e. $a = yy_1=yy_2$

Otherwise, we can assume $yy_1<yy_2$. then $(0,a)$ must be on the segment between $P_1$ and one point in $S_2$

We can enumerate the points in $S_2$, say $Q_i$, and get the intersection of $x=0$ and $P_1Q_i$. Then $(a,0)$ must be the highest point among the intersection points.

$(b,0)$ can be get in the same way. so intersecting a line with a convex hull of a set of points in 2d can be done in O(N).

This approach is wrong.

$\endgroup$
4
  • $\begingroup$ Consider $(-3, -3), (3, 3), (-4, -5), (1,2)$. $\endgroup$
    – John L.
    Jun 10 at 17:46
  • $\begingroup$ Moreover, in some cases neither of the two extreme points $P_1$, $P_2$ are on the boundary of the convex hull. Consider $(-3, 2), (-1, 1), (1, -2), (3, -3)$. $\endgroup$
    – hidanom
    Jun 10 at 18:25
  • $\begingroup$ I mean, neither of them are on the correct edge of the convex hull. The one with the greater $y$ coordinate is, of course, on the boundary. $\endgroup$
    – hidanom
    Jun 10 at 18:35
  • $\begingroup$ @hidanom You are right. My approach is wrong. $\endgroup$ Jun 11 at 3:53

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.