1
$\begingroup$

I am looking for an idea of an algorithm for the following problem:

Give an efficient algorithm to determine whether a polygon P with n vertices is monotone with respect to some line, not necessarily a horizontal or vertical one.

Monotonicity is the crucial part of Polygon Triangulation.

In my opinion the easiest algorithm is sweep plane for testing monotonicity, which is gonna take $O(nlogn)$.

Also there is linear time algorithm of Preparata, but I didn't find it.

If you have any idea of testing monotonicity or you know where to find Preparata's algorithm share it with us.

Thanks!

1 Answers 1

1

I have no idea how Preparata's algorithm looks like, but I think is possible to do it in linear time with almost brute force. For each two consecutive edges check the angle between them and if it is concave, you will have a constraint on the possible directions of monotonicity. If there is something left, then no vertex will cause a problem (after all you have checked every vertex for this), and if there's nothing left, you have your proof that each direction will fail.