# Always a planar-drawn cycle through $n$ points

Given $n$ points in the plane, can we always find a cycle through all of them that has only straight line edges and no edges intersect (planar-drawn)?

Intuitively the answer is yes, but I am struggling with a proof. In the example above, the $2^{nd}$ graph demonstrates an incorrect algorithm, whereas the last graph demonstrates a working algorithm. I have tried using induction.

For different variants there are constraints - this is not always possible if the points are colored (e.g. if two points of one color lies on non-adjacent points of the convex hull and any path between them partitions the other color).

• What about this: first draw the boundary of the convex hull of these points. Then remove the points in this boundary, and repeat. This way you get a nested family of convex polygons. Lastly, remove an edge in each polygon and connect them in a spiral. Dec 18, 2015 at 19:58
• @PietroMajer; does this guarantee a cycle?
– JMP
Dec 18, 2015 at 19:59
• Ops, I was thinking to a simple arc. It could be modified to get a cycle, but FP's construction below is much better. Dec 18, 2015 at 20:02
• @PietroMajer even if this works, we must choose removing edges carefully. Dec 18, 2015 at 20:03
• You have to exclude all $n$ points collinear, i.e., lying on one line. Dec 18, 2015 at 20:16

Yes. Let $A$ be a vertex of a convex hull. Draw rays $AP_1,\dots,AP_{n-1}$ to other points, let them go in this order counted counterclockwise. Then $AP_1P_2\dots P_{n-1}A$ is what you need.

• what if A, P, Q are colinear?
– JMP
Dec 18, 2015 at 20:10
• Then count them from nearest to furthest from $A$.
– eric
Dec 18, 2015 at 20:13

Every shortest cycle through the $n$ points is noncrossing. This can be easily shown by contradiction: if two edges are crossing, they form the diagonals of a convex $4$-gon, and we can replace them by a pair of opposite sides of the $4$-gon (one choice gives a cycle, the other choice gives two cycles). By the triangle inequality, the new cycle is shorter than the original one.

• that might create a new crossing
– JMP
Dec 19, 2015 at 2:31
• Yes, it could. But the length will decrease, and there are only finitely many Hamiltonian cycles, so after a finite number of these operations we will get a noncrossing cycle. This might not be a very efficient algorithm though. Dec 19, 2015 at 2:45

Here is a quote from the first paper cited below: Steinhaus posed a version of your question, which has become known as simple polygonization of a set of points:

1Agarwal, Pankaj K., Ferran Hurtado, Godfried T. Toussaint, and Joan Trias. "On polyhedra induced by point sets in space." Discrete Applied Mathematics 156, no. 1 (2008): 42-54.

25Hugo Steinhaus. One Hundred Problems in Elementary Mathematics. Dover Publications, Inc., New York, 194.

Subsequently, Michael Gemignani removed the general-position assumption, relaxed to not-all-collinear. And then Grünbaum offered a simple proof that leads to an $O(n \log n)$ algorithm.1

Fedor Petrov's solution is known as a star polygonization.

Finding a minimal-area simple polygonization is NP-hard.