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

$\endgroup$
  • 2
    $\begingroup$ Please provide more details. What have you tried? Where did you get stuck? $\endgroup$ – padawan May 4 '18 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 May 4 '18 at 18:44
  • $\begingroup$ @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. $\endgroup$ – nbro May 4 '18 at 21:22
  • 2
    $\begingroup$ https://cs.stackexchange.com/q/2197/20691 is a very related question. $\endgroup$ – nbro May 4 '18 at 23:21
  • 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 May 5 '18 at 12:24
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.

$\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.