# Proving 2D Convex Hull properties

I'm digging through "Computational Geometry" chapter in "Introduction to Algorithms" and there is a notion of convex hull introduced, alongside with Graham Scan algorithm for finding it.

One of the definitions in the book for a convex hull is:

Convex hull of a set of 2D points is the smallest convex polygon containing all points in a set.

The material is all intuitively clear for me, but when I try to prove to myself some elementary properties of 2D convex hull, I fail. In particular, I'm trying to prove the following properties:

• All vertices of convex hull of a set of points form a subset of these points
• Given a set of points, a point with minimal y-coordinate, which also has a minimal x-coordinate is a vertex of convex hull of that set

I just feel my mathematical toolbox is not rich enough to give such proofs. Using just a definition, I cannot get too far, as it doesn't give me much and seems too high level for me (notion of convexity and minimal area seems complex). Is there some particular branch of mathematics I should study before trying to prove that formally? Or maybe all tools I need are already in my toolbox and I should just think harder? Any tips?

• Don't (want to) know how other people think, but for me a "proof" is simply a convincing argument, ipse est (i.e.) not necessarily a formal argument. How could a formal "proof" further clarify your already "intuitively clear" insight, rather than by obfuscating it? – Han de Bruijn Oct 1 '16 at 8:42
• I don't believe my intuition - it is sometimes giving me feeling I understand a topic well when it is not the case. That's why sometimes - like in this case - I'd rather go through formal arguments why something is true, as when I understand proofs well I get a feeling it gives me deeper appreciation for the topics they are describing. – qiubit Oct 4 '16 at 22:01
• Who is the author of the book? – Chill2Macht Oct 6 '16 at 18:12
• It's a classical CLRS algorithm text – qiubit Oct 7 '16 at 13:20

For the second question, you can use a nice property in convex geometry, that is: "Every point on the convex hull is a convex combination of the vertices of the convex hull" In another word, if the vertices of the convex hull are $p_1,p_2,...,p_n$, then for every point $x$ on the convex hull, $x=\sum_{k=1}^n a_kp_k$ where $\sum_{k=1}^n a_k=1$ and $a_k\ge 0$.