patternMinor
The optimal complexity of intersecting a line with a convex hull of a set of points in 2d
Viewed 0 times
convextheoptimallinehullwithsetpointsintersectingcomplexity
Problem
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?
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?
Solution
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).
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).
Context
StackExchange Computer Science Q#152178, answer score: 4
Revisions (0)
No revisions yet.