Recipe

Find the convex hull of a finite point set

Use when: you have finitely many points in \mathbb R^n and need to know which ones are genuine vertices of the hull versus which are redundant

Goal: the subset of points that are actual vertices of \operatorname{conv}(S), with every other point identified as a convex combination of them

Taught in The convex hull and conic hull

1. 1

   Plot or list every point. Look for one that visually sits inside the shape the others sweep out -- that's your first candidate for "redundant."

   Example

   Five points: (0,0),\ (4,0),\ (4,4),\ (0,4),\ (2,2). The first four form the corners of a square; the fifth, (2,2), sits at the square's exact center.

   Why: a hull vertex can never sit inside the shape the other points already form, so an obviously interior point is the first thing worth testing.

2. 2

   Try to write the candidate as \sum\theta_ix_i with every \theta_i\ge0 summing to 1, using the remaining points. Equal weights across a symmetric-looking subset are a natural first try.

   Example

   With \theta_1=\theta_2=\theta_3=\theta_4=\tfrac14 on the four square corners, \tfrac14(0,0)+\tfrac14(4,0)+\tfrac14(4,4)+\tfrac14(0,4)=(2,2) -- it works.

   • the weighted sum reproduces the candidate exactly — the candidate is redundant; drop it from the vertex list.
   • no nonnegative, sum-to-one weights reproduce the candidate — the candidate is a genuine vertex; keep it.

   Why: this is exactly Section 1's convex combination -- a point already blended from others adds nothing a hull built from just those others wouldn't already contain.

3. 3

   Every point that couldn't be written as a combination of the others in Step 2 is a vertex of \operatorname{conv}(S).

   Example

   (0,0), (4,0), (4,4), (0,4) survive -- four vertices of the square-shaped hull, with (2,2) dropped as redundant.

   Why: \operatorname{conv}(S)'s corners are always a subset of S itself, by Section 1's own technical explanation -- nothing outside the original points can ever become a new corner.