The famous "Happy Ending Problem" for quadrilaterals states:

Theorem Given a set of five points in the general position on the plane, there exists a subset of 4 which form the vertices of a convex quadrilateral.

Proof See Wikipedia.

I found an alternative proof based on a parity argument, and I would like to ask for advice in generalizing it.

We define $\sigma$ to $\sigma(p_1, p_2, p_3) = 0 \mod 2$ if the points $(p_1, p_2, p_3)$ lay counterclockwise, and $\sigma(p_1, p_2, p_3) = 1 \mod 2$ if they lie clockwise. Define $Q$ as $$Q(p_1, p_2, p_3, p_4) = \sigma(p_1, p_2, p_3) + \sigma(p_1, p_2, p_4) + \sigma(p_1, p_3, p_4) + \sigma(p_2, p_3, p_4) \mod 2$$

Note this is invariant under permutations of the $p_i$s, so we may regard it as a functions on sets of four points. (The reader should verify it is invariant under transpositions.) For four points $q$ notice that $Q(q) = 0$ if and only if $q$ is a convex quadrilateral. The easiest way to see this is to draw three points in the general position, the three lines that pass through them, and the seven regions they define. 2-color the regions according to if the fourth point in that region will create a convex quadrilateral. You will see a proper 2 coloring implying if drag a point between adjacent regions in addition toggling the parity you will change whether or not the four points are convex.

Proof 2 Let $X$ be a set of five points. Let $X^{(4)}$ be all subsets of $X$ of size 4. If $X$ contains no convex quadrilateral then for all $q \in X^{(4)}$, $Q(q) = 1$. Noting $|X^{(4)}| = 5$, The sum $\sum_{q \in X^{(4)}} C(q)$ is a sum of five odd terms so is odd. But for every triple $i < j < k$, the term $\sigma(i, j, k)$ occurs twice in the sum, and therefore the sum should be even.

This argument completely fails when I tried to use it to show 9 points contain a convex 5-gon. Is there any simple variants which work for larger number of points, even 9?

Edit: In the comments @domotorp asked how many convex pentagons could occur in a set of 9 points. Note not all numbers are possible: If the set contains exactly one concave pentagon (out of a possible of 126) then it contains one concave quadrilateral. That quadrilateral is contained in at least 5 pentagons so our assumption of 125 pentagons is false.

I do not know a good way of iterating through finite sets of points, unique up to convexity. (Help? Is there a good way?) However by randomly generating points, I have been able to generate configurations which contain 1, 2, 3, ..., 86, 87, 88 and 91, 96, 97, 101, 111, 126 pentagons.

  • 4
    $\begingroup$ From your proof it follows that the number of convex 4-gons among 5 points is odd. Could someone smart with databases tell what the possible number of convex 5-gons are among 9 points? $\endgroup$ – domotorp Jul 6 '17 at 7:46
  • 4
    $\begingroup$ This proof relies only on the numbers $\sigma(p_1,p_2,p_3)$ for all $3$-sets $\{p_1,p_2,p_3\}$ (all $3!$ permutations are defined by one value), and you can forget geometry after seeing that we want to find $Q(q)=0$ for some $q$. If a $5$-gon is convex, then all $4$-gons obtained from it are convex. However, for 9 points you can assign values (see here) to the $\sigma(p_1,p_2,p_3)$ so that there is no $5$-set for which $Q(q)=0$ for all $4$-subsets. So more geometry is needed to restrict the values $\sigma(p_1,p_2,p_3)$. $\endgroup$ – Janne Kokkala Jul 6 '17 at 8:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.