¿Cómo pruebo si un polígono es monótono con respecto a una línea?

Es bien sabido que los polígonos monótonos juegan un papel crucial en la triangulación de polígonos .

Definición: Un polígono en el plano se llama monótono con respecto a una línea recta , si cada línea ortogonal a cruza con como máximo dos veces.$P$$L$$L$$P$

Dada una línea y un polígono , ¿existe un algoritmo eficiente para determinar si un polígono es monótono con respecto a ?$L$$P$$P$$L$

$x$$x$$O(n)$

Spoilers ahoy:

IsMonotone (X [0..n-1], Y [0..n-1])
    local_mins ← 0
    para i ← 0 a n-1
        si (X [i] <X [i + 1 mod n]) y (X [i] <X [i-1 mod n])
            local_mins ← local_mins + 1
    return (local_mins = 1)

Si le preocupa que su polígono tenga bordes verticales, use la siguiente subrutina en lugar de la comparación X[i] < X[j]para romper vínculos constantemente:

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

$L$$ax+by=c$IsLess

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))

$x$

1. $x$$\mathcal{O}(n)$

2. Estos dos vértices dividen el límite del polígono en dos curvas: una cadena superior y una cadena inferior.

3. $x$$\mathcal{O}(n)$