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.

6 thoughts on “Covering points with caps”

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

    1. 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. 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. 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. Let’s consider only unit vectors x for now. Then is the projection of x_k onto the direction x. The goal is to choose x that maximizes all these projections, because projection is large when the angle between x and x_k is small.

      The above can be reformulated as: maximize the minimum of subject to condition ||x||=1.

      But the previous problem is equivalent to minimizing ||x|| subject to >= 1. Because if a shorter vector delivers >= 1, then by making it a unit vector we get larger .

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s