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)}...
- 71
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 $...
- 353
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 ...
- 1
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, ...
- 713
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, ...
- 713
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 ...
- 713
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 ...
- 11.9k
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,521
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 ...
- 117
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 ...
- 1,024
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 ...
- 4,577
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_{...
- 11.9k
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; ...
- 11.9k
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 ...
- 213
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 ...
- 1,605
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,605
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 ...
- 4,881
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}+\...
- 79
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 $|...
- 329
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 ...
- 93
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 $\...
- 11
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 ...
- 4,577
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 ...
- 6,338
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 ...
- 4,577
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)
...
- 4,881
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 ...
- 4,577
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 ...
- 1,531
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 ...
- 161
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},...
- 1,950
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 ...
- 1,950
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 ...
- 135
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 ...
- 309
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 ...
- 11
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 ...
- 11.9k
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 ...
- 4,577
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 ...
- 4,577
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, ...
- 4,881
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 ...
- 15.9k
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,868
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,577
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 ...
- 4,577
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,...
- 4,881
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 $\...
- 241
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: ...
- 4,577
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 ...
- 33
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 ...
- 61
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 ...
- 319