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

Question

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$?

Answer 1

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] < X[i+1 mod n]) and (X[i] < 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] < 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))

Answer 2

Here's a more informal, high-level, and, hopefully, intuitive explanation of an algorithm to check if a polygon is "horizontally monotone", i.e. with respect to the $x$-axis.

1. Find the leftmost and rightmost vertices (i.e. the vertices of the polygon with respectively the min and max $x$-coordinate), in $\mathcal{O}(n)$ time (i.e. just iterate once the list of vertices).

2. These two vertices split the polygon's boundary into two curves: an upper chain and a lower chain.

3. Walk from left to right along each chain, verifying that the $x$-coordinates are nondecreasing. This takes $\mathcal{O}(n)$ time.