10
$\begingroup$

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

$\endgroup$
10
$\begingroup$

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))
$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.