[Algorithms] self intersecting polygons

[Nils P. <n.p...@cu...>]

I googled half a day to find a simple answer to this question:

"How do I detect if a polygon (n-gon) is self intersecting or not".

The obvious solution would be to search for edge intersections. This has 
O(n*log(n)) complexity when doing plane/line sweep.

Does a O(n) algorithm exist? and if so, which?

Thanks,
  Nils

(btw, poly-tesselation is fun!)