How do I test if a polygon is monotone with respect to a line?
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] &lt; X[i+1 mod n]) and (X[i] &lt; X[i-1 mod n])
            local_mins ← local_mins + 1
    return (local_mins = 1)


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

IsLess(X, i, j):
    return ((X[i] &lt; X[j]) or (X[i] = X[j] and i &lt; 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 &lt; Dj) or (Di = Dj and i &lt; j))