Return to 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 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?

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?

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

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

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 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-2}$ 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?

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