# 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.

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}$.

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.

## 6 thoughts on “Covering points with caps”

1. David Speyer says:

The planar case can be done by lifting the points (x,y) in R^2 to (x,y,x^2+y^2) in R^3. Let P be the paraboloid { (x,y,x^2+y^2) }. For any point (u,v,w) in R^3, let C be the curve of all points in P such that the line through (x,y,z) and (u,v,w) is tangent to P. Then C projects to the circle (x-u)^2 + (y-v)^2 = u^2+v^2+w in R^2. So you can run the same trick, optimizing u^2+v^2+w over the linear inequalities saying that (u,v,w) lie on the appropriate side of the tangent planes to P at (x_i, y_i, x_i^2+y_i^2).

The trick of lifting planar geometry to the paraboloid is commonly used when computing Delaunay triangulations. http://en.wikipedia.org/wiki/Delaunay_triangulation

1. David Speyer says:

Although I haven’t found it yet, I suspect a sign error in the previous comment. Clearly, the radius should be zero when (u,v,w) lies on P.

1. L says:

This is very neat! Yes, a sign error: the squared radius is u^2+v^2-w, the vertical distance from the point to paraboloid. I wrote a post based on your comment; it’s scheduled for 08/17.

2. Ogami musashi says:

Hello, Thank you for this informative post. I would need you help though. I first came accross this page (1) and also this one (2) then your page. I have trouble understanding why we should minimize x. Isn’t the vector x from origin to the plane? In my brain it says that we should maximize it while constraining the y_i to have a >= 0 scalar product with x (as in (2)). Obviously i’m wrong but can’t find out why.

Thank you!

(1)http://math.stackexchange.com/questions/409217/how-to-find-the-centre-of-vectors-in-3-dimensional-space)