Covering points with caps

Sometimes easy problems should be solved in a hard way.

Problem 1. Given a finite subset of a circle, find a shortest arc containing the set.

Easy way. Sort the points by polar angle; find a maximal gap between points; return its complement as an answer.

Shortest arc
Shortest arc

Hard way. Not only is this approach harder, it also requires an additional assumption: the set is contained in some open semi-circle.

Draw the tangent line at every point {x_k} of the set. It divides the plane into two half-planes. Focus on the closed half-plane {P_k} that does not contain the circle. Find the point {x^*\in \bigcap P_k} that is closest to the center of circle. The line {L} from the center to {x^*} is the line of symmetry of the required arc. Its size is determined by the maximal distance of given points to {L}.

Intersection of halfplanes determined by tangent lines
Intersection of halfplanes determined by tangent lines

Finding {x^*} is a quadratic minimization problem {\|x\|^2\rightarrow \min} with linear constraints, which is not so bad. Still, this is obviously the harder way.


Problem 2. Given a finite subset of a sphere, find the smallest spherical cap containing the set.

A moment’s reflection is enough to see that the easy way is no longer available. What was previously the hard way now becomes a reasonable solution which works in every dimension (provided that the set is contained in an open hemisphere). Assuming the sphere is a unit sphere, all you do is minimize {\|x\|^2} subject to linear constraints {\langle x,x_k\rangle\ge 1 } for every {k}.

Why this works: {\{y:\langle x,y\rangle\ge 1 \}} is a half-space that intersects the sphere along a spherical cap. The smaller {\|x\|} is, the greater is the distance from this half-space to the origin, and the smaller spherical cap is cut off. The constraints ensure that the cap contains the given points.


One might expect the “flat” version of Problem 2, with plane instead of sphere, to be easier. Yet, I don’t see a way to reduce the flat problem to quadratic minimization with linear constraints.

Problem 3. Given a finite subset of the plane, find the smallest disk containing the set.

This is an instance of the problem of finding the Chebyshev center of a set.