5
$\begingroup$

Let $d$ be a norm-based metric in $\mathbb{R}^2$. We are given a $d$-ball with radius 1, and we would like to cover it with objects with diameter 1. How many objects are needed?

In the $\ell_1$ metric, 4 are sufficient (and probably necessary):

enter image description here

Similarly, in the $\ell_\infty$ metric, 4 are sufficient (and probably necessary):

enter image description here

In the $\ell_2$ metric, 7 are sufficient, according to this answer by Joseph O'Rourke:

7 disks covering a disk

For covering with disks, 7 are also necessary (it cannot be covered by 6 disks), but maybe it can be covered by other objects with diameter 1.

QUESTION: is there a finite integer $C$ such that, for every metric $d$, every $d$-ball of radius 1 can be covered by $C$ objects of diameter 1?

NOTE: the following related questions are interesting too:

  • is there a finite integer $B$ such that, for every metric $d$, every $d$-ball of radius 1 can be covered by $B$ $d$-balls of diameter 1?

  • is there a finite integer $A$ such that, for every metric $d$, every $d$-ball of radius 1 can be covered by $A$ $d$-balls of radius $1/2$?

It is easy to see that $C\leq B\leq A$ (the latter follows from the fact that each $d$-ball of radius $1/2$ has diameter at most $1$ by the triangle equality).

EDIT 1: Anton Petrunin showed that $A$ is finite (and therefore $B$ and $C$ are finite too). A followup question is: what are tight upper bounds on these numbers?

I conjecture that $A\leq 16$: we can take the unit ball and apply an affinte transformation on it such that it contains a unit square, and is contained in a square of side-length at most 2 (I am not sure about the 2, but it holds for a triangle, and triangle seems a worst-case for all convex figures). Therefore, we can cover the unit ball by $4\times 4$ squares of side-length $1/2$; each of these is contained in a ball of radius $1/2$. Is the conjecture true? Is it possible to get tighter upper bounds on $A, B$ or $C$?

EDIT 2: in this paper we prove an upper bound $A\leq 25$, as well as motivate the search for tighter bounds: it provides a constant-factor approximation to an NP-hard matching problem.

$\endgroup$
4
  • $\begingroup$ Does the question ask whether, for some fixed type of object, we can do it, or for every fixed choice of object, we can do it, or does it allow that the type of object depends on the metric? $\endgroup$
    – LSpice
    Dec 12, 2022 at 21:22
  • 1
    $\begingroup$ @LSpice the type of object can depend on the metric. It can be any object with diameter 1 in that metric. $\endgroup$ Dec 13, 2022 at 9:01
  • 2
    $\begingroup$ To cover the Euclidean unit disc with 6 objects of diameter 1, divide it into 60-degree sectors. $\endgroup$ Dec 21, 2022 at 19:59
  • $\begingroup$ @NoamD.Elkies Thanks! This already shows that $C<B$ is possible. $\endgroup$ Dec 26, 2022 at 8:16

1 Answer 1

2
$\begingroup$

I assume you mean all metrics induced by norm, otherwise the answer is obviously "no".

For any norm there is a bilipschitz euclidean norm with coefficient $\le 10$. Note that a unit ball in the euclidean plane can be covered $100000000$ balls of radius $\tfrac1{100}$. Whence $C= 100000000$ will do.

$\endgroup$
7
  • $\begingroup$ Shouldn't the small balls have diameter $\frac{1}{100}$, instead of radius $\frac{1}{100}$? $\endgroup$
    – Saúl RM
    Dec 12, 2022 at 17:47
  • $\begingroup$ "For any norm there is a bilipschitz euclidean norm with coefficient ≤10" I did not understand this sentence. Can you give a reference where I can read more about this theorem? $\endgroup$ Dec 12, 2022 at 18:15
  • $\begingroup$ @ErelSegal-Halevi Use the norm induced by Johnson's ellipsoid. $\endgroup$ Dec 12, 2022 at 22:17
  • 1
    $\begingroup$ @ErelSegal-Halevi In case it is helpful: remember that there is a bijection between norms in $\mathbb{R}^n$ and compact convex neighborhoods $K$ of $0$ with $K=-K$ ($K$ is the ball $B(0,1)$ in some norm). Moreover, if the ball is an ellipsoid, then the problem is the same as the problem with Euclidean balls, because an ellipsoid (in $\mathbb{R}^2$, an ellipse) is an affine image of the sphere. Also, for any convex $K$ in $\mathbb{R}^2$ generating a norm, its Outer John ellipsoid (see wikipedia) contains $K$ and is contained in $2K$, so their norms are $2$-Lipschitz respect to each other. $\endgroup$
    – Saúl RM
    Dec 12, 2022 at 22:45
  • 1
    $\begingroup$ @ErelSegal-Halevi by the norm generated by a compact, convex, balanced set I just mean its Minkowski functional. For a reference on why they generate norms see for example theorem 1.39 of Rudin's $\textit{Functional Analysis}$ $\endgroup$
    – Saúl RM
    Dec 15, 2022 at 8:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.