3
$\begingroup$

How can I prove that a convex hull of a finite set of points in the plane is always a convex polygon? This result looks very intuitive, but how can you prove it formally? I thought about taking any convex polygon that contains in it all of the points, and then make it smaller and smaller until one of it's sides meets one of the points, and then do the same to the other sides, but how do you make it formal?

$\endgroup$
3
  • 1
    $\begingroup$ It depends on your definitions. How do you define "convex hull" and "convex polygon"? $\endgroup$ – lhf Sep 7 '20 at 11:22
  • $\begingroup$ @lhf Convex hull of a set $S$ is the smallest convex set that contains all of the points in $S$ (which is also the intersection of all convex sets containing $S$). Convex polygon is a simple polygon which is convex as a subset of $R^2$. $\endgroup$ – Omer Sep 7 '20 at 11:25
  • $\begingroup$ This algorithm gives a proof: en.wikipedia.org/wiki/Gift_wrapping_algorithm $\endgroup$ – lhf Sep 7 '20 at 11:52
0
$\begingroup$

Hint

Denote by $S_n = \{p_1, \dots, p_n\}$ the finite set of points and $\overline{S_n} = \mathrm{Conv}(S_n)$.

Let $\mathcal M = \{M \subseteq S_n \mid \mathrm{Conv}(M) = \mathrm{Conv}(S_n)\}$ and $P$ an element of $\mathcal M$ with the minimum cardinal.

Prove that $P$ is a polygon when ordering its points in an appropriate way, i.e rotation around a point in $\mathrm{Conv}(P)$.

$\endgroup$
2
  • $\begingroup$ I already thought about removing points which are unnecessary. It did not lead me much far. Can you be more specific on how to prove that this is indeed a polygon? $\endgroup$ – Omer Sep 7 '20 at 12:09
  • $\begingroup$ It is a simple polygon as the lines joining the vertices can't cross themselves: if not the rotation around a point won't be monotonous. It is convex as it convex hull is... convex. $\endgroup$ – mathcounterexamples.net Sep 7 '20 at 12:14
0
$\begingroup$

Let $S\subset\Bbb{R}^2$ finite and $C$ the convex hull of $S$. Because $C$ is convex and contains $S$, it also contains every line segment connecting pairs of points in $S$. It follows that $C$ contains every polygon with its vertices in $S$.

Let $P$ be the union of all polygons with vertices in $S$, so that $S\subset P\subset C$. Note that $P$ is itself a polygon because $S$ is finite. Then $P$ is itself convex because it contains every polygon on its vertices. It follows that $C\subset P$ and hence $C=P$, so the convex hull is a polygon.

$\endgroup$
10
  • $\begingroup$ It is not clear to me that $P$ is a polygon. Why is that? $\endgroup$ – Omer Sep 15 '20 at 21:43
  • $\begingroup$ @Omer It is the union of finitely many polygons; there are only finitely many polygons with their vertices in $S$ because $S$ is finite. $\endgroup$ – Servaes Sep 15 '20 at 21:50
  • $\begingroup$ But why is the union of finitely many polygons is a polygon? If we take two disjoint triangles for example, isn't it a counterexample? And even if it is a polygon, why will the vertices still be elements of S? $\endgroup$ – Omer Sep 15 '20 at 21:59
  • $\begingroup$ I guess it depends on what you are willing to call a polygon. It's not hard to see that $P$ is connected however, because it contains every polygon with its vertices in $S$. So in the case of your two disjoint triangles, you should also include the hexagon(s) on these six vertices in the union. $\endgroup$ – Servaes Sep 15 '20 at 22:05
  • $\begingroup$ As for the vertices; this remark was redundant so I have removed it. $\endgroup$ – Servaes Sep 15 '20 at 22:09

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.