## Chapter26Happy Ending Problem Applet

###### Project by: James Cameron McNeil, Xing Wei, Yu Yu, and Sasha Zotine.

$\textbf{Summary:}$ In 1935 Erdős and Szekeres proved the following theorem:

For any positive integer $N\text{,}$ any sufficiently large finite set of $M$ points $S = \{(x_1,y_1),\ldots,(x_m,y_m)\}$ in the plane in general position has a subset of $N$ points that form vertices of a convex $N$–gon.

Particularly, we know that a minimum of $9$ points in general position is required to guarantee the existence of a convex pentagon, $f(5)=9\text{.}$ By Erdős–Szekeres theorem, there exists configurations of fewer than 9 points in which no convex pentagon can be drawn. It can be shown that there exist configurations of 8 points in which NO convex pentagons can be formed.

The goal of this project was to design an interactive web–app where the user attempts to input $N$ points ($N=8$ particularly) in general position in which no convex pentagons can be found. This is a nontrivial problem computationally because there are 8–choose–5 combinations, or 56 possible pentagons one needs to check to ensure no convex pentagons can be formed from a set of 8 properly arranged points in general position. The code was also generalized to detect the existence of a convex quadrilateral ($N=4$) and a convex hexagon ($N=6$).

Below we outline the general ideas behind our code and detection protocols in the case of $N=5\text{.}$

• User inputs $M$ points $S = \{(x_1,y_1),\ldots,(x_m,y_m)\}$ in general position in an interactive display.

• User has an opportunity to try to avoid forming a convex pentagon.

• The built in pentagon detection algorithm alerts the user once when a convex pentagon is found.

The basic structure of the algorithm involves selecting a $5$–element subset of $S\text{,}$ ordering the subset in a counter clockwise arrangement, detection of the convexity or concavity. If the former, done, if the latter then a new unique 5 element set is generated and the algorithm repeats till a convex set is found. If no convex set is found then the program returns a congratulatory message.

Basic structure details:

1. From the indices $I=\{1,2,\ldots,M\}$ the set of all $5$–term combinations are generated $I_i=\{a,b,c,d,e\}\text{,}$ where $a,b,c,d,e$ are unique indices in $I$ and $i=1,2,\ldots, \binom{M}{5}\text{,}$ giving us a set of five elements $S(I_i)=\{(x_a,y_a),(x_b,y_b),\ldots,(x_e,y_e)\}=\{\vec{r}_a, \vec{r}_b,\ldots, \vec{r}_e\}\text{,}$ for a chosen $I_i\text{.}$

2. There are $\binom{5}{2}=10$ different ways of connecting all points in the set $S(I_i)\text{,}$ only one of which forming a pentagon. As will be outlined below, the ordering of these points must be established to “draw” the edges defining the encircling pentagon: a counter clock wise arrangement is chosen.

3. Ordering: Define the mean of the set $S(I_i)$ as $\overline{\vec{r}}_i=\text{average}(S(I_i))=(\overline{x},\overline{y})$ and define the vector $\vec{d}_j=\vec{r}_j - \overline{\vec{r}}_i=(x_j-\overline{x},y_j-\overline{y})$ for all $\vec{r}_j\in S(I_i)\text{,}$ as illustrated in Figure 26.0.1 (left).

The angle made between the positive $x$–direction and $\vec{d}_j$ is $\theta_j\text{.}$ If $y-\overline{y}\gt 0$ then $\theta_j=\arccos((x_j-\overline{x})/h_j)$ where $h_j=|\vec{d}_j|\text{.}$ If $y-\overline{y}\lt 0$ then $\theta_j=2\pi - \arccos((x_j-\overline{x})/h_j)\text{.}$

The set $S(I_i)$ is then oriented in a counter clockwise (CC) fashion into a set of 2D vectors $S(I_i^\prime)$ where $I_i^\prime=CC(I_i)$ and $CC:I_i\to I_i$ is our ordering function so as to yield a monotonic increase in $\theta _j$ on $[0,2\pi)\text{.}$

An example of a CC ordered set of 5 points in the plane is illustrated in Figure 26.0.1 (right) where

\begin{equation*} I_i^\prime=\{(x_{a_1},y_{a_1}), (x_{d_2},y_{d_2}),(x_{e_3},y_{e_3}),(x_{b_4},y_{b_4}),(x_{c_5},y_{c_5}). \end{equation*}
4. Now we define the set of CC oriented edges as vectors $\vec{r}_m=(x_{k_{m+1}}-x_{j_m},y_{k_{m+1}}-y_{j_m})\text{,}$ where $j,k\in I_i\text{.}$ We wish to define a new set of characteristic angles $\phi_m$ of $\vec{r}_m\text{.}$ If $y_{k_{m+1}}-y_{j_m}\gt 0$ then $\phi_m=\arccos((x_{k_{m+1}}-x_{j_m})/H_m)$ where $H_m=|\vec{r}_m|\text{.}$ If $y_{k_{m+1}}-y_{j_m}\lt 0$ then $\theta_j=2\pi - \arccos((x_{k_{m+1}}-x_{j_m})/H_m)\text{.}$

A convex pentagon is detected if $\phi_1\lt \phi_2\lt \phi_3\lt \phi_4\lt \phi_5\text{.}$ If there exist $\phi_{m+1}\leq \phi_m$ the the pentagon is NOT convex and breaks this loop by selecting an new $S(I_t)$ for $t\not= i\text{.}$ In the case $\phi_{m+1}=\phi_m\text{,}$ the given points are not in general position as 3–points can be connected with a straight line. An example of this is illustrated in Figure 26.0.1 (right) in which $\phi_d\lt \phi_e\lt \phi_b\not\lt \phi_c\text{.}$

5. The program continues selecting a new set $S(I_t)\subset S$ for $s\not= i$ until a convex pentagon is found or not found. If you are lucky enough to have chosen a set of 8 points so that no convex pentagon is found for all 56 combinations, the program responds saying “CONGRATULATIONS!”