3
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$
    – Han de Bruijn
    Oct 1, 2016 at 8:42
  • $\begingroup$ 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. $\endgroup$
    – qiubit
    Oct 4, 2016 at 22:01
  • $\begingroup$ Who is the author of the book? $\endgroup$
    – Chill2Macht
    Oct 6, 2016 at 18:12
  • $\begingroup$ It's a classical CLRS algorithm text $\endgroup$
    – qiubit
    Oct 7, 2016 at 13:20

1 Answer 1

Reset to default
2
+100
$\begingroup$

One way to prepare yourself to prove statements about convex hull is to learn about convex geometry and some of their properties.

I don't think you need any advance tool for the first question. You can prove it by assuming a convex hull with at least one vertex that is not an element of the set of points, then showing that you can either delete that point (which reduce the area) or replace that point with some other points that are elements of the set of points.

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$.

(source: https://en.wikipedia.org/wiki/Convex_combination)

$\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.