I am reading [a paper by Szekeres and Peters](https://www.cambridge.org/core/journals/anziam-journal/article/computer-solution-to-the-17point-erdosszekeres-problem/0EC7876789232266D60439A4C00D86D9) on computing the 17-point case of [the Erdős–Szekeres conjecture](https://en.wikipedia.org/wiki/Happy_ending_problem). 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?



Determining if a polygon is convex using relations on orientation of each ordered triple of points
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$.


