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!