Using a paraboloid to cover points with a disk

Find the equation of tangent line to parabola ${y=x^2}$borrring calculus drill.

Okay. Draw two tangent lines to the parabola, then. Where do they intersect?

If the points of tangency are ${a}$ and ${b}$, then the tangent lines are
${y=2a(x-a)+a^2}$ and ${y=2b(x-b)+b^2}$. Equate and solve:

$\displaystyle 2a(x-a)+a^2 = 2b(x-b)+b^2 \implies x = \frac{a+b}{2}$

Neat! The ${x}$-coordinate of the intersection point is midway between ${a}$ and ${b}$.

What does the ${y}$-coordinate of the intersection tell us? It simplifies to

$\displaystyle 2a(b-a)/2+a^2 = ab$

the geometric meaning of which is not immediately clear. But maybe we should look at the vertical distance from intersection to the parabola itself. That would be

$\displaystyle x^2 - y = \left(\frac{a+b}{2}\right)^2 -ab = \left(\frac{a-b}{2}\right)^2$

This is the square of the distance from the midpoint to ${a}$ and ${b}$. In other words, the squared radius of the smallest “disk” covering the set ${\{a,b\}}$.

Same happens in higher dimensions, where parabola is replaced with the paraboloid ${z=|\mathbf x|^2}$, ${\mathbf x = (x_1,\dots x_n)}$.

Indeed, the tangent planes at ${\mathbf a}$ and ${\mathbf b}$ are
${z=2\mathbf a\cdot (\mathbf x-\mathbf a)+|\mathbf a|^2}$ and ${z=2\mathbf b\cdot (\mathbf x-\mathbf b)+|\mathbf b|^2}$. Equate and solve:

$\displaystyle 2(\mathbf a-\mathbf b)\cdot \mathbf x = |\mathbf a|^2-|\mathbf b|^2 \implies \left(\mathbf x-\frac{\mathbf a+\mathbf b}{2}\right)\cdot (\mathbf a-\mathbf b) =0$

So, ${\mathbf x}$ lies on the equidistant plane from ${\mathbf a}$ and ${\mathbf b}$. And, as above,

$\displaystyle |\mathbf x|^2 -z = \left|\frac{\mathbf a-\mathbf b}{2}\right|^2$

is the square of the radius of smallest disk covering both ${\mathbf a}$ and ${\mathbf b}$.

The above observations are useful for finding the smallest disk (or ball) covering given points. For simplicity, I stick to two dimensions: covering points on a plane with the smallest disk possible. The algorithm is:

1. Given points ${(x_i,y_i)}$, ${i=1,\dots,n}$, write down the equations of tangent planes to paraboloid ${z=x^2+y^2}$. These are ${z=2(x_i x+y_i y)-(x_i^2+y_i^2)}$.
2. Find the point ${(x,y,z)}$ that minimizes the vertical distance to paraboloid, that is ${x^2+y^2-z}$, and lies (non-strictly) below all of these tangent planes.
3. The ${x,y}$ coordinates of this point is the center of the smallest disk covering the points. (Known as the Chebyshev center of the set). Also, ${\sqrt{x^2+y^2-z}}$ is the radius of this disk; known as the Chebyshev radius.

The advantage conferred by the paraboloid model is that at step 2 we are minimizing a quadratic function subject to linear constraints. Implementation in Sage:

 points = [[1,3], [1.5,2], [3,2], [2,-1], [-1,0.5], [-1,1]] constraints = [lambda x, p=q: 2*x[0]*p[0]+2*x[1]*p[1]-p[0]^2-p[1]^2-x[2] for q in points] target = lambda x: x[0]^2+x[1]^2-x[2] m = minimize_constrained(target,constraints,[0,0,0]) circle((m[0],m[1]),sqrt(m[0]^2+m[1]^2-m[2]),color='red') + point(points) 

Credit: this post is an expanded version of a comment by David Speyer on last year’s post Covering points with caps, where I considered the same problem on a sphere.