Can a polygon with minimal perimeter self-intersect?

Recipe. Do the following.


  • Throw $N$ random points $(x_0,y_0),(x_1,y_1),x_2,y_2),\cdots,(x_{N-1},y_{N-1})$ in the plane.
    Define $(x_N,y_N)=(x_0,y_0)$ : enumeration is $\mod N$ .

  • These points are joined in a number of ways to form a polygon with $N$ edges. Define “a number of ways” as permutations $\pi$ of the vertex numbering. Vertex $(0)$
    can be left in place without loss of generality.

  • Select the polygon with minimal perimeter i.e. the smallest sum of the edges lengths:
    $$\sum_{k=0}^{N-1}\sqrt{(x_{\pi(k+1)}-x_{\pi(k)})^2+(y_{\pi(k+1)}-y_{\pi(k)})^2}
    = \mbox{minimum}(\pi)$$


Conjecture. Such a polygon does not self-intersect

Picture on the left: Area maximized (and self intersecting).

(Where the area of the polygon is defined as in
this answer)

Picture on the right: Perimeter minimized (same vertices).

Vertex numbering: digit on the left is original, digit on the right is permutation.

enter image description here

Can someone prove or disprove this conjecture?

Solutions Collecting From Web of "Can a polygon with minimal perimeter self-intersect?"