Construction and Motivation
The convex hull is the polygon formed by a tautly wound spool of thread wrapped around a collection of datapoints with thumbtacks stuck over them on a piece of cardboard. This way of visualizing makes the following assumptions most readers of this post are very likely to have unconciously already made:
- That there is an infinite amount of thread available, and as a result of which…
- The distance between any two points the thread connects to form an edge, could potentially be infinite.
This thread and thumbtack example is further advantageous since it makes it explicitly clear why a shape so constructed would be convex. Beginning at, say for example the highest datapoint among all the thumbtacks, and wrapping the thread counterclockwise around the collection of points will always pick for the next vertex of the polygon, some point which will have a height (the y coordinate) obviously smaller than the previous. This is of course only true since we have assumed infinite available thread.