Stretch a Rubber Band Around a Scatter of Points. That Shape Has a Name

Given a scatter of points, consider every shape that contains all of them and has no inward dents, meaning that a straight line between any two points inside the shape stays inside it. There are many such shapes and they all contain the smallest one, which is the shape in question. The physical picture is exact and worth keeping: hammer a nail at each point, stretch a rubber band around the whole lot and let it go. The band settles on the boundary, touching only some of the nails and passing straight over the rest.

Several properties fall out immediately:

• •Its corners are always original points, never new ones
• •Interior points never appear on the boundary
• •The two furthest apart points both lie on the boundary
• •So does any point extreme in any direction whatsoever
• •It can be computed in time close to the number of points
• •The same definition works unchanged in three dimensions and more

The standard methods are simple enough to describe and that is part of why the problem is taught early. One approach starts at the lowest point, sorts the rest by the angle they make with it, then walks through them keeping a running boundary and discarding any point that would create a dent. Another repeatedly wraps around the outside, starting from a point known to be on the boundary and finding the next by choosing the point that everything else lies to one side of, which is intuitive and slower when many points are on the boundary. A third splits the set, solves each half and merges.

The shape is deliberately blind to detail, and knowing what it loses explains when something else is needed. A crescent of points has the same boundary as a solid blob in the same position, because the dent is exactly what the construction fills in. A single distant outlier drags the whole boundary out to reach it. Two separate clusters are enclosed as one shape with a wide empty middle. Where those matter, the alternative is a shape allowed to have dents, which follows the points more closely at the cost of no longer being unique and needing a parameter to say how tightly to cling.

The shape appears as the first step in a long list of practical tasks because it throws away everything irrelevant to questions about extremes. Collision detection in games and robotics tests these simplified shapes before testing complicated ones, since if the simplified versions do not touch, nothing does. Pattern recognition uses it to describe the outline of a detected object compactly. Mapping software uses it to draw the smallest sensible region containing a set of readings. Statistics uses nested versions to find outliers. And any problem asking for the furthest apart pair, the smallest enclosing circle or the widest gap can ignore interior points entirely.

The smallest dent-free shape containing a scatter of points is what a rubber band settles on, and its corners are always original points. Anything extreme in any direction lies on that boundary, so interior points can be discarded before asking about furthest pairs, widest gaps or enclosing circles. It is computed quickly and used as a first pass in collision detection and pattern recognition.