# Convex Hulls

• Mar 18th 2008, 08:30 AM
iknowone
Convex Hulls
Let $\displaystyle V = \left\{v_1, ... ,v_n\right\}$ be a collection of vertices in the plane. Define the maximum convex hull $\displaystyle C$ of $\displaystyle V$ to be the convex polygon with vertices in $\displaystyle V$ such that every point in $\displaystyle V$ is either an interior point or a vertex of $\displaystyle C$.

Define $\displaystyle C_1=\left\{v_1, ... v_m\right\}$ to be the maximum convex hull of $\displaystyle V$ relabling if necessary. With the remaining points $\displaystyle V/ C_1 = \left\{v_{m+1}, ..., v_n\right\}$ recursively define maximum convex hulls $\displaystyle C_2, ..., C_k$.

The picture should be a series of shrinking polygons each completely contained in the previous. Some of this requires proof but I don't think it is too difficult to show that given any finite collection of points in the plane there exists a unique maximum convex hull.

What I would like to do is connect the convex hulls in some minimum way (minimum number of edges) to ensure the resulting graph contains a complete cycle.

Idea:
$\displaystyle \forall i, \forall v \in C_i$ connect $\displaystyle v \text{ to } x \in C_{i+1}$ such that $\displaystyle d(v,x) <= d(v,y), \text{ } \forall y \in C_{i+1}$
In other words connect each vertex on each hull to the closest vertex on the next hull.