3
$\begingroup$

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 enter image description here

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

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ Please provide more details. What have you tried? Where did you get stuck? $\endgroup$
    – padawan
    Commented May 4, 2018 at 8:55
  • $\begingroup$ 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 $\endgroup$
    – mm8511
    Commented May 4, 2018 at 18:44
  • 1
    $\begingroup$ @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. $\endgroup$
    – j_random_hacker
    Commented May 5, 2018 at 12:24
  • $\begingroup$ @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. $\endgroup$
    – EniGma
    Commented May 5, 2018 at 20:26
  • $\begingroup$ @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. $\endgroup$
    – j_random_hacker
    Commented May 5, 2018 at 22:29

1 Answer 1

Reset to default
1
$\begingroup$

This answer is related to the remarkable answer for a similar problem. The only difference is that the OP asked about monotonicity of a polygonal chain, but not about monotonicity of a polygon.

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.

The picture below shows a polygonal chain with four segments. Authorized angles at each internal vertex are marked by green color.

enter image description here

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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