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