Asymptotically optimal algorithm to compute if a line intersects a convex polygon

Question

An O(n) algorithm to detect if a line intersects a convex polygon consists in checking if any edge of the polygon intersects the line, and look if the number of intersections is odd or even.

Is there an asymptotically faster algorithm, e.g. an O(log n) one?

Answer 1

lhf's answer is close to correct. Here is a version that should fix the problem with his.

Let the polygon have vertices v0, v1, ..., vn in counterclockwise order. Let the points x0 and x1 be on the line.

Note two things: First, finding the intersection of two lines (and determining its existence) can be done in constant time. Second, determining if a point is to the left or the right of a line can be done in constant time.

We will follow the same basic idea of lhf to get an O(log n) algorithm. The base cases are when the polygon has 2 or 3 vertices. These can both be handled in constant time.

Determine if the line (v0,v(n/2)) intersects the line (x0,x1).

Case 1: They do not intersect.

In this case the line we are interested in is either to the left or the right of the line splitting the polygon, and so we can recurse into that half of the polygon. Specifically, if x0 is to the left of (v0,v(n/2)) then all the vertices in the right "half", {v0, v1, ... v(n/2)} are on the same side of (x0,x1) and so we know that there is no intersection in that "half" of the polygon.

Case 2: They do intersect.

This case is a little trickier, but we can still narrow down the intersection to one "half" of the polygon in constant time. There are 3 subcases:

Case 2.1: The intersection is between the points v0 and v(n/2)

We are done. The line intersects the polygon.

Case 2.2: The intersection is closer to v0 (that is, outside the polygon on v0's side)

Determine if the line (x0,x1) intersects with the line (v0,v1).

If it does not then we are done, the line does not intersect the polygon.

If it does, find the intersection, p. If p is to the right of the line (v0, v(n/2)) then recurse into the right "half" of the polygon, {v0, v1, ..., v(n/2)}, otherwise recurse to the left "half" {v0, v(n/2), ... vn}.

The basic idea in this case is that all points in the polygon are to one side of the line (v0, v1). If (x0, x1) is diverging away from (v0, v1) on one side of its intersection with (v0, v(n/2)). We know that on that side there can be no intersection with the polygon.

Case 2.3: The intersection is closer to v(n/2)

This case is handled similarly to Case 2.2 but using the appropriate neighbor of v(n/2).

We are done. For each level, this requires two line intersections, a left-right check, and determining where a point is on a line. Each recursion divides the number of vertices by 2 (technically divides them by at least 4/3). And so we get a runtime of O(log n).

Answer 2

I think this article gives a clear O(log n) solution. Find the extremes in the direction perpendicular to the given line.