Determining if a polygon is convex using relations on orientation of each ordered triple of points

Question

I am reading a paper by Szekeres and Peters on computing the 17-point case of the Erdős–Szekeres conjecture. The conjecture states that the minimum number of points in the plane (in general position, no three points collinear) such that any arrangement will contain a convex subset of $n$ points is $$ 2^{n-2}+1 $$

The paper describes an algorithm which tests if a subset of points is convex by checking the orientation of each ordered triple of points. The signature function $\sigma$ maps an ordered triple of points $(a,b,c)$ to $\{+,-\}$, if the three points are oriented clockwise or counterclockwise respectively.

On page 6, the paper gives a convexity condition from 4 relations on the signatures of each ordered triple of points,

Let abcde be any (ordered) set of five points of $S_9$. It forms a convex 5-subset if and only if its Q = 10 triples satisfy one of the four relations (termed convex relations): $$ R_1: \sigma(abc)=\sigma(bcd)=\sigma(cde)\\ \quad R_2: \sigma(abc) = \sigma(bce) = -\sigma(ade)\\ \quad R_3: \sigma(abd) = \sigma(bde) = -\sigma(ace)\\ \quad R_4: \sigma(acd) = \sigma(cde) = -\sigma(abe) $$

And on page 9, there is a similar set of 8 relations for a 6-subset,

Let abcdef be any (ordered) set of six points of $S_{17}$. It forms a convex 6-subset if and only if its ${6 \choose 3} = 20$ triples satisfy one of the eight convex relations: $$ R_1: \sigma(abc)=\sigma(bcd)=\sigma(cde)=\sigma(def)\\ \quad R_2: \sigma(abc) = \sigma(bcd) = \sigma(cdf) = -\sigma(aef) \\ \quad R_3: \sigma(abc) = \sigma(bce) = \sigma(cef) = -\sigma(adf) \\ \quad R_4: \sigma(abd) = \sigma(bce) = \sigma(def) = -\sigma(acf) \\ \quad R_5: \sigma(acd) = \sigma(cde) = \sigma(def) = -\sigma(abf) \\ \quad\quad R_6: \sigma(abc) = \sigma(bcf) = -\sigma(ade) = -\sigma(def) \\ \quad\quad R_7: \sigma(abd) = \sigma(bdf) = -\sigma(ace) = -\sigma(cef) \\ \quad\quad R_8: \sigma(acd) = \sigma(cdf) = -\sigma(abe) = -\sigma(bef) $$

From these two quotes, it seems that there are a set of $2^{n-3}$ relations for $n$ point convexity. How are these convex relations derived? And how can the set of convex relations for an arbitrary number of points be found?

Answer 1

It's important to note that when it talks about ordered points, this is ordered by $x$-coordinate and not (as one might otherwise suppose) by traversing the edges of the polygon.

Suppose we have $n$ points, $p_1$ to $p_n$, ordered by $x$-coordinate. Observe that $p_1$ and $p_n$ are on the convex hull. Now draw a line $p_1 - p_n$ and partition the points $p_2, \ldots, p_{n-1}$ by which side of the line they fall. Call the subset of points which are below or on the line $q$ and the subset of points which are above or on the line $r$.

For the polygon to be convex, $q$ must be a chain of anti-clockwise turns, and $r$ must be a chain of clockwise turns. Therefore $$\sigma(q_1 q_2 q_3) = \sigma(q_2 q_3 q_4) = \cdots = \sigma(q_{|q|-2} q_{|q|-1} q_{|q|}) = -\sigma(r_1 r_2 r_3) = \cdots = -\sigma(r_{|r|-2} r_{|r|-1} r_{|r|})$$

We get $2^{n-3}$ cases by considering which subset of $p_3, \ldots, p_{n-1}$ is in the same chain as $p_2$.