# Questions tagged [packing-and-covering]

The packing-and-covering tag has no usage guidance.

185
questions

0
votes

0
answers

48
views

### Upper bound of covering number of $\ell_1$-ball under $\ell_2$-norm

Let $B^n_1 = \{x : \Vert x\Vert_1 ≤ 1\}$ be the $\ell_1$-norm unit ball. How can we prove the covering of $B^n_1$ under $\Vert\cdot\Vert_2$ satisfies
$$\sqrt{\log N(B^n_1, \Vert\cdot\Vert_2, \epsilon)}...

0
votes

0
answers

67
views

### When do covering and packing have the same behavior: when does $\log N_p(\delta) \lesssim \log N_c(\delta)$ for all $\delta > 0$ hold?

Let $X \equiv (X, d)$ denote a compact metric space and let $N_c(\delta), N_p(\delta)$ denote the covering and packing numbers of space, respectively. Here $\delta > 0$.
Evidently we always have $...

0
votes

1
answer

93
views

### A variation of Set Cover

Suppose we have $n$ sets $\{S_i\}_{i=1}^n$, each containing exactly $k$ of the numbers from $1,...,n$. The union of all these sets will cover $1,...,n$. We know $i \in S_i$ for all $i$. We need to ...

3
votes

1
answer

113
views

### If $X,X'$ have the same $\varepsilon$-packing numbers and $f:X \to X'$ surjective $1$-Lipschitz, then $f$ is an isometry

Let $(X, d)$ be a compact metric space.
We say that $\{x_1, \cdots, x_n\} \subseteq X$ is an $\varepsilon$-covering of $X$ if for any $x \in X$, there exists $i \in \{1, \ldots, n\}$ such that $d(x, ...

2
votes

1
answer

123
views

### Are two metric spaces isometric if they have the same $\varepsilon$-covering and $\varepsilon$-packing numbers for all $\varepsilon>0$?

Let $(X, d)$ be a compact metric space.
We say that $\{x_1, \cdots, x_n\} \subseteq X$ is an $\varepsilon$-covering of $X$ if for any $x \in X$, there exists $i \in \{1, \ldots, n\}$ such that $d(x, ...

2
votes

1
answer

165
views

### Are two metric spaces isometric if they have the same $\varepsilon$-covering numbers for all $\varepsilon>0$?

Let $(E, d)$ be a metric space. For $\varepsilon>0$, we define two notions of $\varepsilon$-covering number as follows, i.e.,
$N_\varepsilon^o (E)$ is the smallest number of open balls whose radii ...

1
vote

0
answers

16
views

### Regular covering of planar pointsets with convex polygons

Question:
What is known about the problem of covering a finite set of $\mathbb{P}$ of points in the plane with convex polygons
that have the same number $m$ of points from $\mathbb{P}$ as corners
and ...

1
vote

0
answers

60
views

### Packing number of sparse vectors

The packing number is defined as follows (defintion 4.2.4 here):
A subset $K$ of a normed space $(\mathbb{X},\Vert\cdot\Vert)$ is called $\epsilon$-separated, if $\Vert x-y\Vert> \epsilon$ for all ...

1
vote

0
answers

18
views

### Path cover with sets of nodes

I am considering the following variant of the path-cover problem. I have an acyclic directed graph G=(V,E). Moreover, the set V is partitioned into $V=V_1 \cup ... \cup V_k$ (these sets are pairwise ...

5
votes

1
answer

182
views

### Covering unit-radius balls with unit-diameter objects

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

3
votes

0
answers

104
views

### Hemisphere containing the maximum number of points scattered on a sphere

Consider a set of points $x_1, \ldots,x_n$ on $\mathbb{S}^{k-1}$ (the unit sphere in $\mathbb{R}^k$). The goal is finding the hemisphere which contains the maximum number of $x_i$'s. Basically, we ...

2
votes

0
answers

150
views

### Minimal overlap required to cover a sphere with caps is greater than expected for many caps

My question is derived from Covering the surface of a sphere with circles with least overlap on Math SE.
In the referenced question, the problem of completely covering a sphere with the smallest ...

5
votes

1
answer

176
views

### Which pyramids fill space?

Let us define a pyramid as a convex polyhedron with one quadrilateral face and four triangular faces.
Question: How many pyramids (or families of pyramids) are known that can fill 3D space without ...

0
votes

0
answers

29
views

### Finding optimal cycle covers with vertex cardinality constraints

Let $G(V,E)$ be an asymmetric graph of order $n$ without parallel edges or self loops.
Let further $\lbrace\nu_i\in\mathbb{R}\rbrace$ be a set of weights assigned to the vertices and $\lbrace\omega_{...

0
votes

1
answer

41
views

### Dual equivalence of minimum feedback-vertex sets and cycle packing

it is known that the duals of feedback-set problems are set-packing problems; in the context of digraphs the feedback set are either a minimal set of vertices or edges that hit every oriented cycle; ...

6
votes

1
answer

280
views

### Does finite Hausdorff dimension imply finite packing dimension?

In other words, does there exist a metric space $(E,\rho)$ with finite Hausdorff dimension but infinite packing dimension?
Here are my thoughts:
I know that it is generally hard to relate Hausdorff ...

4
votes

0
answers

137
views

### Approximation of a convex shape in the $d$-dimensional Euclidean space for $d\gg 1$

We are given a convex shape $C$ lying inside the hypercube $[0,1]^d$ in the $d$-dimensional Euclidean space. Let the volume of $C$ be $\tfrac12$ (I guess nothing changes for any other fixed constant ...

5
votes

1
answer

144
views

### $d$-ball approximation for $d\gg 1$ with a convex hull of random points on its boundary

Given a $d$-ball $\mathcal{S}^{d}$, let $P_n$ a set of $n$ points selected uniformly at random on the boundary $\mathcal{S}^{d-1}$ of $\mathcal{S}^{d}$. Let $\mathcal{C}_n$ the convex hull of $P_n$. ...

1
vote

1
answer

121
views

### Packing number in finite-dimensional normed spaces

I am working on a paper and quoted the following result from these lecture notes.
Where can I find a reference to this result either in a book or a paper, that I can cite?
(I looked on the course ...

1
vote

1
answer

195
views

### Covering numbers for products of functions from two spaces?

Exercise (HW1): Let $\mathcal{F}$ and $\mathcal{G}$ be classes of measurable function. Then for any probability measure $Q$ and any $1 \leq r \leq \infty$,
(i) $N_{[]}\left(2 \epsilon, \mathcal{F}+\...

2
votes

0
answers

101
views

### Sudakov's lower bound type inequality for supremum of Chi-squared random variables

Let $\varepsilon$ be $n$-dimensional standard Gaussian veector, i.e., $\varepsilon \sim N_n(0, I_n)$. Let $\mathcal{P}$ be a subset of symmetric projection matrices in $\mathbb{R}^{n \times n}$ with $|...

2
votes

0
answers

105
views

### Covering/Bracketing number of monotone functions on $\mathbb{R}$ with uniformly bounded derivatives

I am interested in the $\| \cdot \|_{\infty}$-norm bracketing number or covering number of some collection of distribution functions on $\mathbb{R}$.
Let $\mathcal{F}$ consist of all distribution ...

1
vote

0
answers

191
views

### Bound on covering number of Lipschitz functions – missing part in proofs of Kolmogorov et al

Given a metric space $(\mathcal{X},\rho)$ and $\mathcal{A}\subset\mathcal{X}$ totally bounded, i.e. $\mathcal{A}$ has a finite $\varepsilon$-covering for any $\varepsilon>0$. Consider $\...

2
votes

1
answer

145
views

### On rigid packings of the plane with a constraint

This post continues Thinnest rigid packings of the plane
A packing of the plane with copies of any shape is called rigid (or "stable") if every unit is fixed by its neighbors, i.e., no unit ...

1
vote

1
answer

203
views

### For $x_1,...,x_n$ iid random on sphere of radius $\sqrt{d}$ in $R^d$, what is a good upper-bound on min distance of $x_{n}$ from the other $x_i$'s?

Let $n$ and $d$ be large positive integers with $n \le d^\gamma$, for some absolute constant $\gamma>0$; i.e., $n$ is at most polynomial in $d$. Let $x_1,\ldots,x_n,x_{n+1}$ be drawn iid from the ...

1
vote

0
answers

46
views

### Which pentagon gives least packing density?

We extend Which convex pentagon gives least packing density? by going from convex pentagons to general ones.
Question: Which pentagon gives the least packing density on the Euclidean plane?
Note: All ...

3
votes

0
answers

102
views

### Covering number $C^k$-balls in $C(\mathbb{R}^n)$

Fix a positive integer $n$ and and an non-negative integer $k$. The Arzela-Ascoli theorem guarantees that for a given positive integer $k$ and a given $L>0$ the set
$$
Ball_{C^{k,1}([0,1]^n)}(0,L)
...

3
votes

1
answer

156
views

### On the thinnest cover of the plane by a given planar convex region

Is the following claim valid?
Claim: Given any planar convex region C, the thinnest cover of the plane with copies of C cannot have any region where more than 2 copies overlap. In general, the ...

1
vote

0
answers

82
views

### Lower bound estimate for the sum $\sum \text{diam}(U)^d$ over all countable covers of a cube

This question is inspired from the definition of Hausdorff measure. Let $C$ be a closed unit hypercube in $\mathbb R^d$ (side length equal to one, including boundary. The cube itself is at top ...

2
votes

0
answers

78
views

### Can Chang and Wang's proof of Thue’s Theorem on circular packing be extended into other dimentions?

The simplicity of Chang and Wang's proof of Thue’s Theorem (link on arxiv) on circular packing took me by surprise. Have similar ideas been found helpful in other dimensions? For example, partition ...

0
votes

0
answers

51
views

### packing numbers of the unit balls in Euclidean spaces and the dimensions

Let $k$, $m$ and $n$ be positive integers. Let $r$ be a positive real number.
The $n$-th ordered $r$-disk configuration space on the Euclidean space $\mathbb{R}^{mk}$ is
$$
F_r(\mathbb{R}^{mk},...

0
votes

1
answer

115
views

### packing numbers and configuration spaces of the torus

Let $S^1$ be the unit circle of radius $1$.
For any $k\geq 1$, let the $k$-dimensional torus $T^k= \underbrace{S^1\times S^1\times\cdots\times S^1}_k$ be the $k$-fold self-Cartesian ...

2
votes

0
answers

132
views

### Covering number bound for the Sobolev space $W^{1,1}(E)$, with $E \subset \mathbb{R}^n$

Let $E \subset \mathbb{R}^n$ have finite diameter $D(E)= \sup_{x,x' \in E}\Vert x-x' \Vert_n$. Let $W^{1,1}(E)$ denote the class of functions $f$ on $E$ admitting integrable first order weak ...

1
vote

1
answer

248
views

### Covering number in the space of symmetric matrices

Let $S_n(\mathbb{R})$ be the set of symmetric matrices of size $n \times n$. Note $\|\Theta\|_{0}$ the number of nonzero elements of a matrix $\Theta$ and $\|\cdot\|_F$ the Froebenius norm. Consider ...

1
vote

0
answers

1k
views

### How to fill a rectangle with smaller rectangles of given sizes?

I have a problem. I try to find an algorithm to fill up a given rectangle with smaller ones. Something like in this picture:
I know the size of the big rectangle, the size of all the little ...

2
votes

1
answer

129
views

### Generating short Hamilton cycles from complete graphs

Let $G(V,E)$ be a complete symmetric graph without self-loops or parallel edges; depending on the context the edges may however be interpreted as a pair of antiparallel arcs of equal weight.
A vertex ...

2
votes

1
answer

131
views

### Packing densities of non-centrally symmetric planar convex regions

Reference: https://en.wikipedia.org/wiki/Smoothed_octagon
Background: The smoothed octagon is conjectured to have the lowest maximum packing density of the plane of all centrally symmetric convex ...

1
vote

0
answers

210
views

### Why Densest packing of equal spheres in three dimensions is not 88.86? [closed]

I placed four spheres of radius R at vertices of a tetrahedron of edge length 2R .When I calculated density I got 88.86.Actualy I wanted to calculate what is the maximum number of earth that can be ...

1
vote

0
answers

59
views

### A Variant of the Malfatti Problem

See https://en.wikipedia.org/wiki/Malfatti_circles for an introduction to Malfatti's problem.
The above page also states that for n >3, the question of whether a greedy method (at each step, the ...

1
vote

1
answer

133
views

### Effect of snowflaking on doubling constants

This question is related to this one. Let $(X,d)$ be a metric space, let $\epsilon\in [0,1)$ and consider the snowflake $(X,d^{1-\epsilon})$. Suppose that $(X,d)$ has a finite doubling constant, ...

1
vote

1
answer

76
views

### Worst convex compact set for translational packings of $\mathbb R^d$

A (translational) packing of a convex compact subset (with non-empty interior) $\mathcal C$ of $\mathbb R^d$ is a union
of translated non-overlapping (but perhaps touching) copies
of $\mathcal C$.
The ...

22
votes

0
answers

348
views

### What is the covering density of a very thin annulus? Is it $\frac{\pi\sqrt{51\sqrt{17}-107}}{16}$?

Take some very small $\epsilon>0$, and consider the annulus/ring given by the set $\{(r,\theta)\ |\ 1-\epsilon\le r\le1\}\subset \mathbb{R}^2$.
We wish to place translated copies of this annulus ...

1
vote

0
answers

303
views

### Which polygons tessellate the hyperbolic plane?

The packing fraction of a packing in some space is the fraction of the space filled by the figures making up the packing.
It is well known that in Euclidean geometry, all triangles and all ...

4
votes

2
answers

258
views

### Which convex pentagon gives least packing density?

Among all convex pentagons, does the regular pentagon give least packing density?
Further question: For each $n > 6$, is the regular $n$-gon the minimum of packing density?
An analogous question ...

8
votes

0
answers

351
views

### Covering number estimates for Hölder balls

Let $\alpha \in (0,1]$ and $L>0$. The Arzela-Ascoli Theorem guarantees that the set $X(\alpha,L)$ of $f:[-1,1]^n\rightarrow \mathbb{R}^m$ with $\alpha$-Hölder norm at-most $L$ is compact in $C([-1,...

9
votes

1
answer

191
views

### Which unimodular lattices $L\subset \mathbb R^2$ minimize $f_t(L):=\sum_{ v\in L} e^{-t \|v\|_2}$? (for parameters $t>0$)

$\DeclareMathOperator\SL{SL}\DeclareMathOperator\SO{SO}$Consider the lattices in $\SL(2,\mathbb R)(\mathbb Z^2)$ up to rotation. The space of such lattices can be identified with the modular surface $\...

1
vote

3
answers

135
views

### On packing axisymmetric bodies in 3D

Consider any 3D body with an axis of rotational symmetry (e.g. cone, cylinder...) and packing the 3d space efficiently with infinitely many copies of this body. Is the following claim valid?
Claim: ...

3
votes

1
answer

96
views

### Covering radius of a lattice from relevant vectors

Let $L$ be an $n-$dimensional lattice. The Voronoi region of $L$ is given by
$$
\mathcal{V}(L)=\big\{x\in\mathbb{R}^n~|~ \|x\|_2\leq \|x-v\|_2~\forall v\in L\setminus\{0\}\big\}.
$$
Considering the ...

6
votes

1
answer

249
views

### How many Hamming spheres of radius 1 does it take to cover the cube?

I am looking for the sharpest known upper bound on $K(n, 1)$ as $n \rightarrow \infty$. This is the minimal cardinality of a (not-necessarily linear) covering code of $\{0, 1\}^n$ of radius 1.
In ...

0
votes

1
answer

94
views

### Covering number of the conditional distribution function

Suppose $Y$ is a random variable in $\mathbb{R}^d$, and we want to find the covering number
\begin{equation*}
\mathcal{F} = \big\{ F_{Y|W} (y | W) : y \in \mathbb{R}^d \big\}
\end{equation*}
where ...