Given a set of n points is it always possible to construct a non self intersecting polygon?
Asked
Active
Viewed 1,840 times
2
-
Closed polygon with these as only vertices? We need conditions, take $n$ collinear points. – André Nicolas Jan 05 '13 at 06:39
-
Polygon that does what? – Alex Becker Jan 05 '13 at 06: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 05 '13 at 06: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 05 '13 at 07:01
-
2@EwanDelanoy Why is this necessary? The polygon only needs to be simple, not convex. – Erick Wong Jan 05 '13 at 07:15
-
@ErickWong : you’re right, I was only talking about the convex case. – Ewan Delanoy Jan 05 '13 at 10:44
1 Answers
7
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.
proan
- 118