Not very hard to prove, then the breakage-line must create EQUAL ANGLES with sides, connected by it. This idea immediately gives the O(N^3) algorithm. But it could be improved even to O(N). :)

Edited by author 20.08.2008 20:22

It could be corners instead of sides for the following input.
6
0 0
2 1
4 0
4 4
2 3
0 4

to Erick Wilts

CONVEX poligon