Questions tagged [packing-and-covering]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
4
votes
2answers
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
0answers
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
1answer
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
1answer
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
1answer
192 views

Wrapping juggling balls

...
0
votes
0answers
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
1answer
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
1answer
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
1answer
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
0answers
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
1answer
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
0answers
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
1answer
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
0answers
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
0answers
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
2answers
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
0answers
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
0answers
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
1answer
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
1answer
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
1answer
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
3answers
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
0answers
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
2answers
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
2answers
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
0answers
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
2answers
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
1answer
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
0answers
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
0answers
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
1answer
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
2answers
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
4answers
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
2answers
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
0answers
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
1answer
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
1answer
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
1answer
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
1answer
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
3answers
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
4answers
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
0answers
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
1answer
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
3answers
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
2answers
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 ...