Imagine you have a 2D polygon (a 2D closed polygonal chain to be more precise). How do you check if it contains self-intersections? It can be convex or concave, oriented clockwise or counter-clockwise.
Now, I could just run a standard O(N log N) algorithm to check if any two segments cross. But I believe that because we have some additional structure -- the order of the segments and the fact that each two consecutive segments meet at endpoints -- a simpler and faster (maybe O(N)?) algorithm could be devised.
Any ideas?