How do I test if a polygon is monotone with respect to a line?

It's well known that monotone polygons play a crucial role in polygon triangulation.


Definition: A polygon $P$ in the plane is called monotone with respect to a straight line $L$, if every line orthogonal to $L$ intersects $P$ at most twice.

Given a line $L$ and a polygon $P$, is there an efficient algorithm to determine if a polygon $P$ is monotone with respect to $L$?

Hint: A generic simple polygon is monotone with respect to the $x$-axis if and only if it has exactly one vertex whose $x$-coordinate is smaller than its neighbors. This observation immediately suggests an $O(n)$-time algorithm, at least if no edge of your polygon is vertical.

Spoilers ahoy:


IsMonotone(X[0..n-1], Y[0..n-1])
local_mins ← 0
for i ← 0 to n-1
if (X[i]

If you're worried that your polygon might have vertical edges, use the following subroutine in place of the comparison X[i] < X[j] to consistently break ties:

IsLess(X, i, j):
    return ((X[i] < X[j]) or (X[i] = X[j] and i < j))

Finally, if $L$ is some other line of the form $ax+by=c$, modify IsLess as follows:

IsLess(X, Y, i, j):
    Di ← a·X[i] + b·Y[i]
    Dj ← a·X[j] + b·Y[j]
    return ((Dj < Dj) or (Di = Dj and i < j))

StackExchange Computer Science Q#1577, answer score: 11