Convex hull

We can think of almost any available object as a point, which is a powerful abstraction. All devices on a network can be seen as billions of connected dots. GPS navigation shows moving objects as points, whose position is updated in real time. Image documents extracted with machine learning methods can be seen as a catalog of points with certain similarity characteristics that are then organized into different clusters. Seeking the shortest path that visits each city once and then returns to the starting point, means solving the traveling salesman problem for a given set of points. Seeking minima/maxima on a convex polygon (or manifold in higher dimensions) may require going though a lot of vertices. Giving a sheet of paper with numbered dots to a child allows it to connect them until an unsuspected figure becomes visible. Bezier curves as a design tool would be useless without a set of anchor points.

Points seem to be everywhere, although we usually don’t seem to think about that.

If we placed an elastic band around all of them, we would get the smallest enclosing area (convex hull). This could be the only area where it is economical to place expensive wire to connect things in a network; the only area in which a marketing campaign should be started; the only area in which measures to reduce radiation make sense; the only area where it would be feasible to clean the ocean from oil leakages. To find this, case-specific measurements at each point can give clarity whether the inclusion of this point in the set is justified.

We can try to visualize how the convex hull works by drawing points on a canvas after each mouse click. Each time a point is added to the set, the convex hull algorithm returns a list of the points which lie on the hull. All we need to do is to connect them. Clicks inside the enclosed area don’t have any effect, because this doesn’t change the maximal distance between all available points. Clicks outside the area expand it, because the new maximal distances exceed those previously available. Two well-known algorithms for convex hulls are Graham scan and Qhull. I found this implementation of Qhull that led to this simple demo. I hope that you find it useful.