# Questions tagged [packing-and-covering]

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

204
questions

2
votes

0
answers

135
views

### How many unit cubes are needed to 'hide' a unit cube fully in 3D?

Question: What is the smallest number of nonoverlapping unit cubes that can hide a unit cube C - in the sense that every ray emanating from the boundary of C meets the interior or the boundary of one ...

29
votes

2
answers

2k
views

### Packing an upwards equilateral triangle efficiently by downwards equilateral triangles

Consider the problem of packing an upwards-pointing unit equilateral triangle "efficiently" by downwards-pointing equilateral triangles, where "efficiently" means that there is ...

2
votes

0
answers

38
views

### Covering base sets $X$ with a subset family satisfying a "partial covering property"

Let $X$ be an $n$ element base set. Suppose I have a subset family $\mathscr{F} \subset 2^X$ satisfying the following property:
(*) For any subset $Y \subset X$, we can find an element $F \in \mathscr{...

0
votes

1
answer

102
views

### Fractal sets and dimensions

Can we construct two sets $E$ and $F$ meeting the following criteria
$\dim_H(E) = \dim_H(F) = \dim_H(E ∩ F)$
$\dim_P(E), \dim_P(F)$, and $\dim_P(E ∩ F)$ are distinct?
Here $\dim_H$ denotes the ...

0
votes

0
answers

27
views

### Packing number lower bound for sparse vectors

Let $t \in (0, 1)$ and define $P_t(k)$ to be cardinality of the largest set of $t$-separated points (i.e., for any distinct pair of points, the Euclidean distance is strictly larger than $t > 0$) ...

0
votes

0
answers

11
views

### What are known tightest bounds on packing number over hypothesis class with semi-metric distance?

Let $\mathcal{H}$ denotes a hypothesis class we define the semi-metric on $\mathcal {H}$:
$\|h_1 - h_2 \|_{\mathcal{L}_1} = \underset{x \sim \mathcal{D}}{\mathbb{P}}[h_1(x) \neq h_2(x)]$.
Are there ...

1
vote

0
answers

143
views

### Optimal covering trails for every $k$-dimensional cubic lattice $\mathbb{N}^k := \{(x_1, x_2, \dots, x_n) : x_i \in \mathbb{N} \wedge n \geq 3\}$

After a dozen years spent investigating this particular class of problems, I finally give up and I wish to ask you if any improvement is achievable from here on.
The general problem is as follows:
Let ...

3
votes

1
answer

344
views

### Electricity division and bin packing

In the electricity division problem, there is a powerhouse that supplies $s$ kilowatt of electricity. There are $n$ households. The connection size of household $i$ is $d_i$.
The problem is that $s &...

8
votes

3
answers

1k
views

### How many non-orthogonal vectors fit into a complex vector space?

I am sitting on a problem, where I have a complex vector space of dimension $D$ and a set of normalized vectors $\{v_k\}$, $k\in\{1,2,\dots,N\}$ that are supposed to satisfy
$$\lvert\langle v_j\vert ...

11
votes

1
answer

392
views

### Smallest sphere containing three tetrahedra?

What is the smallest possible radius of a sphere which contains 3 identical plastic tetrahedra with side length 1?

0
votes

0
answers

47
views

### Optimal packing and covering of a triangle with squares

We continue from Another variant of the Malfatti problem.
Given a triangle T and a number n, how to cover it with n squares (of possibly different dimensions) such that the sum of the areas (...

1
vote

1
answer

62
views

### Covering convex regions with disks optimizing on area and perimeter

Question: Are there planar convex regions $R$ and integers $n$ with the property: if $R$ is covered by $n$ disks of possibly different sizes such that (1) the total area of the covering disks is ...

2
votes

0
answers

77
views

### Another variant of the Malfatti problem

We try to add to A Variant of the Malfatti Problem
As stated in the Wikipedia entry on Malfatti circles, it is an open problem to decide, given a number $n$ and any triangle, whether a greedy method ...

1
vote

0
answers

131
views

### A comparison between packing and covering as classes of problems

We continue from Bounds for the Dispersal Problem in convex regions and Bounds for minimax facility location in a convex region
Let us consider the classes of problems:
Given a convex region $R$ and ...

2
votes

1
answer

95
views

### The problem of finding the smallest number of copies of a certain shape that can be placed into a space to make fitting another copy impossible

Packing problems often ask for the largest number of some identical shape that can fit in a given space without overlapping, if they are placed optimally.
I'm interested in the opposite question:
Q. ...

1
vote

1
answer

67
views

### Lower bounding the infimum of a random process

Let $X_{t}=\sum_{i=1}^n(1+s\cdot w_i)t_i\sin(t_i)$ where $t\in T=[-\pi/2,\pi/2]^n/\{\vec 0\}$, $w_i$ are iid standard gaussian variables, $s$ is a scalar denoting the strength of Gaussian noise.
How ...

1
vote

2
answers

101
views

### the infimum of a random process

Let $X_{t}=\sum_{i=1}^n(1+s\cdot w)\sin(t_i)$ where $t\in T=[-\pi/2,\pi/2]^n/\{\vec 0\}$, $w\sim\mathbb{N}(0,1)$, $s$ is a scalar denoting the strength of Gaussian noise. How to find the condition on $...

2
votes

1
answer

142
views

### Bounding random process

Def
$\{X_t\}_{t\in T}$ is called Lipschitz for metric $d$ on $T$ if there exists a random variable $C$ such that
$$|X_t-X_s|\leq Cd(t,s),\text{ for all }t,s\in T.$$
Lemma
Suppose $\{X_t\}_{t\in T}$ is ...

8
votes

1
answer

359
views

### You have $n$ rectangles of area $1$ and variable height. Pack as many as possible in a semicircle of area $n$. How many leftovers will there be?

You have $n$ rectangles of area $1$ and variable height. Pack as many of these rectangles as possible in a semicircle of area $n$. How many leftover rectangles will there be, in terms of $n$?
How to ...

0
votes

0
answers

365
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

42
views

### Covering triangles with mutually congruent planar regions - optimally

We continue from this old post: From a given triangle, to cut 2 mutually congruent convex pieces that together 'use' maximum area of the triangle and go from partitioning to covering.
Given ...

0
votes

0
answers

75
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

152
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

126
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

132
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

229
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

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

2
votes

1
answer

151
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

27
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

201
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

129
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

242
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

204
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

1
answer

66
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

383
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

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

7
votes

1
answer

175
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

130
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

458
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

162
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

240
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

339
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

148
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

215
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

48
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

139
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

175
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

94
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

90
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

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