In any set of 9 points in $\mathbb{R}^2$ a convex pentagon exists

311 Views Asked by At

In any set of 9 points in $\mathbb{R}^2$ with no triple of points on the same line a convex pentagon exists.

My attempt: I suppose I need to consider some convex hulls. If the convex hull has $\geq 5$ points, just take it. Else consider convex hull of the points inside. Here I don't understand how to finish the "bruteforce".

1

There are 1 best solutions below

5
On

Erdos&co solved the happy ending problem by considering the slopes of the sides of the convex envelope and applying the Erdos-Szekeres/Dilworth's theorem: every sequence with $n^2+1$ elements has a monotonic subsequence with $n+1$ elements.