# Questions tagged [packing-and-covering]

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

105
questions

**4**

votes

**2**answers

103 views

### An arrangement of entangled squares

Is there an arrangement of finitely many axes-parallel squares in the plane, of $k$ different colors, such that:
The squares of each color are pairwise-disjoint;
Each square overlaps at least $4$ ...

**1**

vote

**0**answers

26 views

### Separation of balls in the torus

Let $X_1, \dots, X_N$ be $N$ balls of radius $R<<1$ in $[0,1]^d$ such that $N R^d \leqslant R^{\alpha}$ for some $\alpha > 0$ and $d(x_i,x_j)\geqslant 2R$ for any $i\not=j$.
The assumption ...

**2**

votes

**1**answer

80 views

### Packing a Riemannian manifold with disjoints balls

Let $M$ be a smooth Riemannian manifold with riemannian measure $\mu$. I don't suppose that $M$ is complete. Can we find a finite or countable disjoint collection of open (or closed) and relatively ...

**1**

vote

**1**answer

74 views

### Covering number of $l_2$ Ball in $\mathbb{R}^d$

What is the covering number $N(\epsilon, B_2, ||\cdot||_2)$ of a ball $B_2$ in $\mathbb{R}^d$ of radius $r$ under the $l_2$ norm?

**5**

votes

**1**answer

192 views

**0**

votes

**0**answers

19 views

### Covering number of $c$-transform of a collection of functions

I'm trying to understand the concepts of covering and packing of collection of functions on a metric space. Thanks in advance for any input.
Let $\mathcal H$ be a collection of functions $\mathcal X \...

**5**

votes

**1**answer

254 views

### Can I cover a compact set by balls {B} such that {2B} has bounded overlap?

Suppose I have a compact set $K \subset B_1(0) \subset \mathbb{R}^n$. Can I always find a family of open balls $\{B_{r_j}(x_j)\}$ such that
$x_j \in K$ and $B_{r_j}(x_j) \subset B_1(0)$ for each $j$;
...

**6**

votes

**1**answer

151 views

### NP-completeness of a covering problem

I was wondering about the complexity of the following covering problem. Let $B_i,\,i=1,\ldots,n$ be a set of unit disks in $\mathbb{R}^2$. The problem is to decide whether there exists $C\subset\{1,\...

**5**

votes

**1**answer

178 views

### Stronger version of Besicovitch covering theorem

I'm wondering if the following strengthening of the Besicovitch covering theorem holds: Suppose $A\subset\mathbb R^n$ is a bounded subset and suppose $x\mapsto r_x$ is a function $A\to(0,\infty)$. Is ...

**0**

votes

**0**answers

20 views

### Is there a simple algorithm to fit rectangles of differing sizes into a larger rectangular-container through one side

Imagine a shipping container (in the two-dimensional length-width dimension). Let's further assume there is a queue of parts waiting to be fit into this container. This queue is not infinite but ...

**6**

votes

**1**answer

200 views

### Asymptotic bound on minimum epsilon cover of arbitrary manifolds

Let $M \subset \mathbb{R}^d$ be a compact smooth $k$-dimensional manifold embedded in $\mathbb{R}^d$. Let $\mathcal{N}(\varepsilon)$ denote the minimal cardinal of an $\varepsilon$-cover $P$ of $M$; ...

**1**

vote

**0**answers

94 views

### Subdividing a Compact Bounded Curvature Manifold into Charts with Bounded Lipschitz Constant

Let $M \subset \mathbb{R}^d$ be a compact smooth $k$-dimensional manifold embedded in $\mathbb{R}^d$. Let $\mathcal{N}(\epsilon)$ denote the size of the minimum $\epsilon$ cover $P$ of $M$; that is ...

**4**

votes

**1**answer

90 views

### Uniform inequality of the form $\text{Proba}(\sup_{v \in [-M,M]^k}|p^Tv-\hat{p}_n^Tv| \le \epsilon_n) \ge 1 - \delta$

Let $M > 0$, $k$ be a positive integer, and $\mathcal V:=[-M,M]^k$. Finally, let $p \in \Delta_k$, (where $\Delta_k$ is the $(k-1)$-dimensional probability simplex) and let $\hat{p}_n$ be an ...

**1**

vote

**0**answers

35 views

### Covering a simplex efficiently by efficiently describable polytopes?

Take a standard simplex or cube in $\mathbb R^n$.
Is there a way to cover it with $O(poly(\log n))$ convex polytopes each describable by only $O(poly(\log n))$ half-plane inequalities?
If not what ...

**1**

vote

**0**answers

59 views

### Polytopes that can be efficiently described and efficiently covered by cubes or simplices?

Is there a bounded convex polytope $\mathcal P\subseteq\mathbb R^n$ with $m$ vertices, whose vertex vectors span $\mathbb R^n$ (so $m$ is $\Omega(n)$) and just $O(poly(\log n))$ half-plane ...

**3**

votes

**2**answers

222 views

### When can any graph $G$ be expressed as a union of $\alpha(G)$ complete graphs?

If for any graph $H$ we define $\alpha(H)$ to be the cardinality of any maximum size indepedent set in $H$. Then under what conditions can any graph $G$ be expressed as a union of $\alpha(G)$ complete ...

**3**

votes

**0**answers

119 views

### Fitting $\frac1n\times\frac1{n+1}$ rectangles into the unit square [duplicate]

Consider the set of rectangles $r_n | n \in \Bbb N$ such that rectangle $r_n$ has shape $\frac1n\times\frac1{n+1}$. The total area composed by one copy of each $r_n$ as $n$ ranges from $1$ to ...

**21**

votes

**0**answers

241 views

### Can 4-space be partitioned into Klein bottles?

It is known that $\mathbb{R}^3$ can be partitioned into disjoint circles,
or into disjoint unit circles, or into congruent copies of a real-analytic curve
(Is it possible to partition $\mathbb R^3$ ...

**5**

votes

**1**answer

132 views

### Algorithm for MaxMin diversity problem on hypercube?

The Maximum Minimum Diversity Problem (MMDP) can be roughly stated as follows:
Let $S$ be a set of points, $k \in \mathbb{N}$. Find the $k$-element subset $M$ of $S$ such that the minimal distance $...

**9**

votes

**1**answer

335 views

### Packing regular tetrahedra of edge length 1 with a vertex at the origin in a unit sphere

Consider the following problem:
How many regular tetrahedra of edge length 1 can be packed inside a unit sphere with each one has a vertex located at the origin?
The answer is at least 20, forming ...

**1**

vote

**1**answer

156 views

### Growth rate of bounded Lipschitz functions on compact finite-dimensional space

Let $\mathcal X$ be a metric space of diameter $D$ and "dimension" (e.g doubling dimension) $d$. Let $L \in [0, \infty]$ and $M \in [0, \infty)$ and consider the class $\mathcal H_{M,L}$ of $L$-...

**4**

votes

**0**answers

134 views

### Tiling squares with oblongs

An oblong is a rectangle whose width and length are consecutive integers: 1x2, 2x3, 3x4, etc. Does N exist such that it is possible to split the first N oblongs into 2 or more non-intersecting sets so ...

**7**

votes

**0**answers

35 views

### Inefficient covering by translates

While trying to answer this question, I arrived at another question:
How many translates of $\{0,1\}^n$ does it take to cover $\mathbb F_3^n$?
The broader context is: consider a set $S$ and a ...

**1**

vote

**0**answers

62 views

### Upper bounds on $\epsilon$-covers of arbitrary compact manifolds

Let $M \subset \mathbb{R}^d$ be a compact $k$-dimensional manifold embedded in $\mathbb{R}^d$. Let $\mathcal{N}(\epsilon)$ denote the size of the minimum $\epsilon$-cover $P$ of $M$, that is for every ...

**4**

votes

**0**answers

114 views

### Lower bound on $\epsilon$-covers of arbitrary manifolds

Let $M \subset \mathbb{R}^d$ be a $k$-dimensional manifold embedded in $\mathbb{R}^d$. Let $\mathcal{N}(\epsilon)$ denote the size of the minimum $\epsilon$-cover $P$ of $M$, that is for every point $...

**3**

votes

**0**answers

166 views

### Lattice points in a rotated product-of-balls

Fix $U$ unitary over $\mathbb{R}^{K},$ take $U_n=I_{n\times n}\otimes U$ and denote the unit ball at 0 in $\mathbb{R}^n$ as $B^n$. For $d_1,\dots,d_K>0$, fix $S_n:=U_n\left(\prod_{k=1}^K d_k B^n\...

**7**

votes

**3**answers

468 views

### Coverage of balls on random points in Euclidean space

We have n points randomly distributed in a d-dimensional unit hypercube. We randomly sample k of those points and center a ball with radius r on each of those k points. Does there exist an estimate of ...

**5**

votes

**0**answers

233 views

### How to pack 27 $a\times b\times c$ blocks into a cube of side $a+b+c$ with some kind of symmetry?

Recently I stumbled on the problem quoted here about a geometric proof of the AM-GM inequality $$(a_1+\cdots+a_n)^n\ge n^n a_1\cdots a_n$$ by packing $n^n$ rectangular $ n$-dimensional boxes of sides $...

**1**

vote

**2**answers

230 views

### Lower bound on misclassification rate of Lipschitz functions in terms of Lipschitz constant

Important note
@MateuszKwaśnicki in the comment section has raised a fundamental issue with the current statement of the problem. I'm trying to bugfix it.
Setup
I wish to show that a Lipschitz ...

**6**

votes

**2**answers

397 views

### VC dimension, fat-shattering dimension, and other complexity measures, of a class BV functions

I wish to show that a function which is "essentially constant" (defined shortly) can't be a good classifier (machine learning). For this i need to estimate the "complexity" of such a class of ...

**10**

votes

**0**answers

451 views

### Which finite sets could be packed into a square?

This question is inspired by an interesting visualization of the finite levels of von Neumann's hierarchy on Adam P. Goucher's blog, Complex Projective 4-Space.
The problem starts with a two-...

**2**

votes

**2**answers

157 views

### Counting triples family with double shared elements

We have a set of elements $S=\{1,2,3, . . . , N\}$ and family $F$ of $N$ triples of elements in $S$ ($N$ is a multiple of 3). Each element of $S$ appears in exactly three triples. The elements in each ...

**1**

vote

**1**answer

297 views

### Packing number of Lipschitz functions

For some $L>0$ say ${\cal L}$ is the space of all $L-$Lipschitz functions mapping $(X,\rho) \rightarrow [0,1]$ where $(X,\rho)$ is a metric space.
For any $\alpha >0$ do we know of a ...

**6**

votes

**0**answers

74 views

### Packing points in a lattice

Let $L$ be the square or triangular lattice in the plane, with nearest neighbors having distance 1. Has anyone studied the problem of finding the maximum (okay, supremum) density achieved by a subset ...

**1**

vote

**0**answers

189 views

### Sphere packings with antipodal (unequal) spheres

Let $\|\cdot\|_2$ denote the Euclidean norm, let $\langle \cdot, \cdot\rangle$ denote the standard dot product, and let $\mathcal{S}^{d-1} = \{\mathbf{x} \in \mathbb{R}^d: \|\mathbf{x}\|_2 = 1\}$ ...

**6**

votes

**1**answer

484 views

### Randomly covering a sphere

Let $S$ be the $n$-dimensional unit sphere in the Euclidean space. Further,
let $X_1,\ldots,X_k$ and $Y_1,\ldots,Y_m$ be iid $S$-valued random variables with common (unknown) distribution $\mu$. With $...

**9**

votes

**2**answers

253 views

### Density of a saturated random packing of congruent circles

The problem of the expected density of a saturated random packing of unit circles in the plane can be described as follows.
In a circular region $C$ of a large radius pick a point at random and draw ...

**52**

votes

**4**answers

4k views

### Is there a mathematical and information theoretic explanation for this cube packing phenomenon?

I saw this unintuitive result on dice packing:
A jumble of thousands of cubic dice, agitated by an oscillating
rotation, can rapidly become completely ordered, a result that is hard
to produce ...

**11**

votes

**2**answers

357 views

### Dodecahedral rolling distance

Let a dodecahedron sit on the plane,
with one face's vertices on an origin-centered unit circle.
Fix the orientation so that the edge whose indices are $(1,2)$ is horizontal.
For any $p \in \mathbb{R}...

**2**

votes

**0**answers

56 views

### Packing net of simplex

For given $d$, we can define the simplex as follows,
$S=\{(x_1,x_2,\cdots,x_d):x_1\geq x_2\geq \cdots\geq x_d\geq 0,\sum x_i=1\}$.
We can define the distance on $S$ as $L_1$ distance.
An $\epsilon$ ...

**9**

votes

**1**answer

206 views

### Thinnest covering of the plane by regular pentagons

Q. Is it known what is the thinnest covering of the infinite plane by regular pentagons?
By covering I mean every point of the plane is covered.
By thinnest I mean the proportion of the plane covered ...

**4**

votes

**1**answer

206 views

### Equation of state for hard rods

Some context:
For ideal gases, the thermodynamic equation of state is the well-known:
$$
pV = nRT \tag{1}
$$
where $n$ is the amount of substance, $R$ the universal gas constant and $P,V,T$ are ...

**2**

votes

**1**answer

192 views

### Packing number of $\ell_1$ ball in $\ell_{\infty}$ metric

Consider the $d$-dimensional $\ell_1$ ball $\mathbb B_d=\{x\in\mathbb R^d: \|x\|_1\leq 1\}$, where $\|x\|_1=\sum_{i=1}^d{|x_i|}$. I'm interested in the maximum size of the (finite) subset $S\subseteq\...

**3**

votes

**1**answer

169 views

### packing with special sets in high dimensional Euclidean space

Let $\lambda$ be Lebesgue measure on $[0,1]$. For $\mathbf{x}=(x_1,x_2,..,x_k)\in[0,1]^k$, define $$A(\mathbf{x}):=\{(y_1,\dots,y_k)\in [0,1]^k: \text{there exist intervals }I_1,\dots,I_k \text{ in }[...

**27**

votes

**3**answers

3k views

### Can squares of side 1/2, 1/3, 1/4, … be packed into three quarters of a unit square?

My question is prompted by this illustration from Eugenia Cheng’s book Beyond Infinity, where it appears in reference to the Basel problem.
Is it known whether the infinite set of squares of side $\...

**10**

votes

**4**answers

331 views

### Sequential addition of points on a circle, optimizing asymptotic packing radius

Suppose I have to put $N$ points $x_1, x_2, \ldots, x_N$ on the circle $S^1$ of length 1 so as to achieve the largest minimum separation (packing radius). The optimal solution is the equally spaced ...

**1**

vote

**0**answers

63 views

### Packing the box $[0,X^{\delta_1}] \times [0,X^{\delta_2}] \times [0,X^{\delta_3}] \subseteq \mathbb{R}^3$ with cubes

Let $0 < \delta_1 \leq \delta_2 \leq \delta_3 \leq 1$, and consider the box $B := [0,X^{\delta_1}] \times [0,X^{\delta_2}] \times [0,X^{\delta_3}] \subseteq \mathbb{R}^3$. Let $X > 3$ say. Is it ...

**2**

votes

**1**answer

185 views

### Packing of anisotropic objects

The most famous version of packing problems deals with perfectly symmetrical shapes such as spheres. But how about anisotropic shapes? More prcisely, if we want to compare spherocylinders (cylinders ...

**5**

votes

**3**answers

363 views

### Exact bin packing the harmonic series: references?

Given $n$ and $B_n= \lceil H_n \rceil$, where the latter is the $n$th harmonic number $\sum^n_{i=1} 1/i$, for most $n$ it is easy to pack the first $n$ terms of the harmonic series into $B_n$ many ...

**4**

votes

**2**answers

400 views

### Minimum number of rectangles in a polygon

Given a polygon and dimension $d$, find a minimum partition of rectangles that has either of its dimensions equal to $d$.
Example:
Consider the following diagram:
I want to cover maximum shaded ...