Assume that P is a closed polyline
in which no three consecutive vertices lie on the same line. The
following linear-time algorithm to check if P is the boundary of a convex
polygon does not work:
If every consecutive sequence of three vertices along P form a left-turn,
then say that P is convex. Otherwise, say that P is not convex.
Draw an example polyline which the algorithm incorrectly
decides is the boundary of a convex polygon.
Fix the algorithm without increasing the asymptotic running