# Linear-time algorithm to check monotonicity of polygonal chain

A polygonal chain $C$ is called monotone with respect to a straight line $L$, if every line orthogonal to $L$ intersects $C$ at most once.

I want to design a linear-time algorithm to check whether there exists a line $L$ such that a given chain $C$ with $n$ vertices is monotone relative to $L$, and find such a line.

My idea is to take an angel of monotone chain and transfer it to the unit circle and suppose there is a line L ! like this

But I don't know how to find a good solution that the L exist

• Please provide more details. What have you tried? Where did you get stuck? – padawan May 4 '18 at 8:55
• are we working in $\mathbb{R}^2$ ? if so, rotate the plane (e.g. take a rotation matrix and apply it to each point) so that the (rotated) y axis is orthogonal to $L$. Order your points lexicographically with respect to this rotation, and simply run the classic Bentley Ottman line sweep algorithm – mm8511 May 4 '18 at 18:44
• @mm8511 You did not understand the problem. In this case, we don't know $L$. We want to find a $L$ which would make $C$ monotone w.r.t $L$. Also, ordering points lexicographically would take $\mathcal{O}(n\log n)$ time. – nbro May 4 '18 at 21:22
• https://cs.stackexchange.com/q/2197/20691 is a very related question. – nbro May 4 '18 at 23:21
• @EniGma: To show you have at least thought about this problem yourself, try completing the following sentence: If the polygon is _____, then it is monotone with respect to every line. – j_random_hacker May 5 '18 at 12:24

The algorithm idea is the same - we need to determine ranges of "authorized" angles for normals to $L$ looking at the adjacent chain segments. An angle is considered authorized if a normal with this angle defines such a straight line $L$, that all the straight lines, orthogonal to $L$, intersect the chain not more than once. In case of a polygon it was enough to look at concave vertices only, but in our case we must look at all the internal vertices.
If an intersection of all the $(n-1)$ ranges of authorized angles isn't empty, then the polygonal chain is monotone, and the line $L$ exists. This algorithm apparently will take $O(n)$ steps.