The optimal complexity of intersecting a line with a convex hull of a set of points in 2d

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?

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).

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

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. 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.

• Consider $(-3, -3), (3, 3), (-4, -5), (1,2)$. Jun 10 at 17:46
• 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)$. Jun 10 at 18:25
• 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. Jun 10 at 18:35
• @hidanom You are right. My approach is wrong. Jun 11 at 3:53