# Non Self Intersecting Polygons?

Given a set of n points is it always possible to construct a non self intersecting polygon?

-
Closed polygon with these as only vertices? We need conditions, take $n$ collinear points. –  André Nicolas Jan 5 '13 at 6:39
Polygon that does what? –  Alex Becker Jan 5 '13 at 6:40
@AndréNicolas I want to know given any random non collinear points is it always possible to construct a non self-intersecting closed polygon. –  harish.venkat Jan 5 '13 at 6:56
An obviously necessary and sufficient condition is that the set of points be "non-reentrant", i.e. no point is inside the convex hull of the other points. –  Ewan Delanoy Jan 5 '13 at 7:01
@EwanDelanoy Why is this necessary? The polygon only needs to be simple, not convex. –  Erick Wong Jan 5 '13 at 7:15

Choose a point $x_0$ of your set and order the other points around $x_0$ counter-clockwise. Label them $x_1,x_2,\ldots x_{n-1}$ according to that order. You get a non intersecting polygon and $x_0$ is in its kernel.