$n$ points in the plane can be connected with $n-1$ clockwise, non-intersecting line segments from any starting point

Question

This conjecture is based on a mobile game that I've published. The object of the game is:

• Given $n ≥ 3$ points in the Cartesian plane in general position (no $3$ of those points are a straight line):
• Connect all the points with $n - 1$ line segments, drawn continuously (without lifting pencil from paper). Drawing lines in this way forms a permutation of the set of $n$ points, with each line segment being defined by the $n-1$ subsequences of $2$ consecutive points in that permutation. (No line segment is drawn between the first and last points in the permutation.)
• Every subsequence of $3$ consecutively connected points must be clockwise oriented in the order that they were connected.
• No two of the line segments may intersect.

Equations that precisely define clockwise orientation and line intersection are provided under the "Insights" section of this post.

I've already proven that every instance of this game is solvable if the player gets to choose the point at which they start: Start at a point on the convex hull of the set of points, then continue making connections in a clockwise spiral to minimize each successive angle between line segments until every point has been reached.

Example solution:

However, I conjecture that the game is also solvable by using any arbitrary point as the starting point, even if it's not on the convex hull of all the points.

I have not yet manually created a counterexample to this conjecture, and I've also searched millions of possible levels using a computer program without finding a counterexample. However, I have yet to formally prove the conjecture.

Clarification:

Here's another wording of the problem:

Given a set of $n ≥ 3$ points $\{P_1, P_2, ..., P_n\}$ in general position, and given an arbitrary point $Q$ from that set, does there always exist a permutation of that set satisfying the following conditions:

• The first element of the permutation is $Q$
• None of the following line segments intersect with each other: $\overline{P_i P_{i+1}}$ for each $i \in [1, n-1]$
• Referring to $P_i$, $P_{i+1}$, and $P_{i+2}$ as $(A_x, A_y)$, $(B_x, B_y)$, and $(C_x, C_y)$ for each $i \in [1, n-2]$, the following condition is always satisfied: $\begin{vmatrix}(B_x - A_x)&(B_y - A_y)\\(C_x - A_x)&(C_y - A_y)\end{vmatrix}<0$

Alternative strategy:

If an alternative conjecture can be proven where $Q$ is the last element of the permutation instead of the first element, then the original conjecture also holds.

Reasoning: If the original conjecture holds for a set of points $S$, then the alternative conjecture holds for $S'$, where $S'$ has the points from $S$ reflected across a given arbitrary line (such as the y-axis).

Insights:

Whether two line segments intersect depends upon whether trios of their points are clockwise-oriented. This correspondence may be usable to generalize the problem, though I am not yet sure how.

Let $c(A, B, C)$ be true iff A, B, and C are clockwise-oriented and false otherwise. Let $i(A, B, C, D)$ be true iff $\overline{AB}$ and $\overline{CD}$ intersect with each other and false otherwise. Then:

$c(A, B, C) = (\begin{vmatrix}(B_x - A_x)&(B_y - A_y)\\(C_x - A_x)&(C_y - A_y)\end{vmatrix}<0)$

$i(A, B, C, D) = (c(A, B, C) \oplus c(A, B, D)) \land (c(C, D, A) \oplus c(C, D, B))$

The following identities hold on the function $c$:

$c(A, B, C) = c(B, C, A) = c(C, A, B)$

$c(A, B, C) \oplus c(C, B, A)$ always evaluates to true

The function $f(N)$ that gives the number of sets of N points that are distinct (defined below) is given by A000930, where $f(N)$ is the Nth element of that sequence. (Obviously, $f(1)$ and $f(2)$ are meaningless in the context of this problem.) For example, there is only one distinct set of $3$ points — they form a triangle. For $4$ points, there are $2$ distinct sets — one with a convex hull of 4 points and one with a single point within a convex hull of 3 other points.

Distinctness for the purpose of this result is defined by:

• the number of times the convex hull of the set of points can be removed before no points remain (i.e. the number of nested convex hulls in the initial set of points), and
• the numbers of points on each of the nested convex hulls.

I believe, but have not yet formally proven, that the solution for any set of points $S$ is generalizable to any other set of points $T$ if $S$ and $T$ are not distinct by the above definition.

Insights from answers:

• Carlyle proved that for a set of points $S$, a solution can always be found if the initial point is in $T$ or $U$, where $T$ is the convex hull of $S$, and $U$ is the convex hull of $(S - T)$.
  • It follows that a solution can be found for any initial point in a set of $6$ or fewer points.

Insights from comments:

Thank you so much to everyone who's left comments! Here is a summary of the ideas and insights derived from my and others' comments.

• There have been misconceptions about the meaning of "clockwise". This term is precisely defined in the "clarification" and "insights" sections of my question.
• Observe the manner in which the following set of points is connected according to the rules in the problem statement: https://i.sstatic.net/gOMgp.png.
• The above set of points does not generalize to all sets of points with 3 convex hulls within each other (e.g. 3 convex hulls inscribed within concentric circles). Why does this not generalize? Consider the case of 4 convex hulls inscribed within concentric circles. Here is the general solution (with an arbitrarily large number of points on each). Here is a specific case, with a different solution than the general case.

Mobile game screenshots:

These screenshots illustrate the conjecture in the context of the mobile game ("Clockwise!" by me, Roy Sianez, available on the iOS App Store within the US). I'm attaching them as an image because the App Store link may not show the product page outside of the US.

Answer 1

Slight improvement: It is always possible to start on the second nested convex hull as well.

Firstly, by second nested convex hull, I mean the convex hull of the points obtained by removing all the points in the convex hull of the original set. (All the trivial cases such as a set with only one point not on the convex hull can be dealt with separately)

It is fairly straightforward to see why this is the case. Given a set of points $S$ and a point $x$ on the second nested convex hull of $S$, we can draw a line through $x$ that bisects $S$ into a region containing only points from the convex hull, and another region containing the rest of $S$. Below is an illustration of such a line drawn through such a point (please help me center this image):

The starting point is circled, and the line drawn is a line that bisects the plane into a region containing only points from the original convex hull, and the rest.

From here on, you can simply go to the most anti-clockwise point on the convex hull above the bisection line, call it $y$:

and complete the spiral as if you were completing it for the set of points $S\setminus\{x\}$ starting on the point $y$ which is on its convex hull, and this completion is guaranteed to not intersect the segment connecting $x$ to $y$, since none of the non-convex hull points of $S$ are above the bisection line, while the line segment connecting $x$ and $y$ is above the bisection line.

In general, if one starts on a non-convex hull point, then any path through the points satisfying the conditions of the problem will necessarily contain all but one line segment on the convex hull. This partial result came from trying to think how one might cleverly choose which line segment to omit, so that one of the spirals going in from one of the points adjacent to the omitted segment starts on the required point, since the path can then be completed in a way analogous to what is described above (I am leaving out some details mostly because I am still struggling to formalise this) but perhaps one can do a sort of induction on the number of nested convex hulls, to show that you can always cleverly choose an edge to omit, but my attempts at this have failed

**Edit, description of an algorithm I believe works, but have not been able to verify:

Take the starting point and find the nested hull that it lies on, draw a line that passes through the two line segments adjacent to the starting point (connecting it to the other points on its hull) now take the orientation of this line and start at one side of the set of points, and start sweeping it across, whenever the line sweeps past a point, neglect that point and calculate the new hulls with the remaining points. I believe that this procedure will always have a step where the starting point is isolated inside the most central hull, at this step, take a point just above the line, on the outermost hull and spiral inwards, anti-clockwise. This spiral is guaranteed to end on the starting point. Then take all those points below the line, and start on the rightmost one on the outermost hull just below the line, and spiral clockwise, then simply connect the two starting points of the spiral, and you have a solution. The struggle is proving that at some step the starting point is isolated in the innermost hull. Here are some diagrams showing the algorithm in action, hopefully someone can make it rigorous:

First, draw the nested convex hulls,and find a line going through the line segments adjacent to the starting point (the starting point is circled):

Now, shift this line all the way down (away from the point) and start sweeping it across:

Each time it passes a point, neglect that points, and draw the nested hulls for the points that remain, the "centers" of the nested hulls start collapsing towards the starting point, and eventually surpass it, but we are interested in finding the step at which the starting point appears isolated in the central hull:

At this point, take the rightmost point above the line, and spiral in anti-clockwise from that point (circled in red), also, complete the spiral below the line, starting with the rightmost point below the line:

Now connect the spirals, to obtain a full solution:

Answer 2

(this is supposed to be a comment, but I couldn't figure out how to add pictures in the comment sections).

@Carlyle's idea is very nice. I just want to point out one thing: the choice of the sweeping line cannot be arbitrary.

Consider this example of $6$ points. Suppose we want to start from $D$. Then one cannot choose the sweeping line to be close to parallel to $EF$, as then $B$ will be removed first, and $D$ would lie on the convex hull. Instead, one must carefully choose the line so that $C$ and $F$ is removed.