8
$\begingroup$

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)?

planar cycle

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).

$\endgroup$
5
  • 1
    $\begingroup$ 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. $\endgroup$ Dec 18, 2015 at 19:58
  • $\begingroup$ @PietroMajer; does this guarantee a cycle? $\endgroup$
    – JMP
    Dec 18, 2015 at 19:59
  • $\begingroup$ Ops, I was thinking to a simple arc. It could be modified to get a cycle, but FP's construction below is much better. $\endgroup$ Dec 18, 2015 at 20:02
  • $\begingroup$ @PietroMajer even if this works, we must choose removing edges carefully. $\endgroup$ Dec 18, 2015 at 20:03
  • 7
    $\begingroup$ You have to exclude all $n$ points collinear, i.e., lying on one line. $\endgroup$ Dec 18, 2015 at 20:16

4 Answers 4

15
$\begingroup$

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.

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

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.

$\endgroup$
2
  • $\begingroup$ that might create a new crossing $\endgroup$
    – JMP
    Dec 19, 2015 at 2:31
  • 6
    $\begingroup$ 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. $\endgroup$
    – Jan Kyncl
    Dec 19, 2015 at 2:45
14
$\begingroup$

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:


  Steinhaus


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.

$\endgroup$
2
$\begingroup$

 


The answer is yes.
First we draw a cycle with the outmost vertices such that other vertices are within the cycle. (This is step 2 in above picture.) Then we repeat this for vertices that are not on the first cycle and draw the second cycle. We repeat this until all vertices lie on a unique simple closed cycle. Now we delete an edge from each two adjacent cycles and connecting vertices such that two cycles exchange in one longer cycle. Then repeat this until we have had a cycle consists all vertices.

$\endgroup$
2
  • $\begingroup$ (I incorporated your figure.) $\endgroup$ Dec 19, 2015 at 16:17
  • $\begingroup$ For completeness, this approach requires a proof that there always exists a pair of edges on nested cycles that can be removed and replaced to connect the two cycles to one. $\endgroup$ Dec 19, 2015 at 16:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.