Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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).
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.
