# 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? 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 May 4 '18 at 18:44
• @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. May 5 '18 at 12:24
• @j_random_hacker I add my thought to the question. If the polygon is (in the plane ) , then it is monotone with respect to every line. May 5 '18 at 20:26
• @EniGma: All polygons are 2D shapes, so they are all "in the plane", so I'm not sure what you mean. A polygon in the shape of the letter C is not monotone with respect to a horizontal line, because some vertical lines intersect it twice. May 5 '18 at 22:29

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.