0
$\begingroup$

How to prove this: The minimum area convex polygon enclosing a set of points is the convex hull of the points.

$\endgroup$
2
  • $\begingroup$ Which definition for convex hull are you using? $\endgroup$ – Michael Biro Oct 26 '16 at 14:27
  • $\begingroup$ the convex hull of a set of points S is the set of all convex combinations of points of S. $\endgroup$ – Coder44 Oct 26 '16 at 14:32
0
$\begingroup$

From the comments, your definition is: The convex hull of a set of points S is the set of all convex combinations of points of S. Define the minimum area convex polygon enclosing S as $A$ and the convex hull of S as $C$.

  1. $A$ is convex and contains the points in $S$, so $A$ must contain the convex combinations of the points in $S$. Can you conclude that $C \subseteq A$?
  2. Both $A$ and $C$ are convex and enclose the points of $S$, so $A \cap C$ is convex and encloses the points of $S$. What does that mean about $A \cap C$ if $A$ has minimum area? In particular, can you conclude that $A \subseteq C$?
$\endgroup$
2
$\begingroup$

Hint: The convex hull may be defined as the intersection of all convex sets containing the given set $S$. So the convex hull is contained in any convex polygon containing $S$.

$\endgroup$

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.