Questions tagged [packing-and-covering]
The packing-and-covering tag has no usage guidance.
31
questions
96
votes
7
answers
19k
views
Can we cover the unit square by these rectangles?
The following question was a research exercise (i.e. an open problem) in R. Graham, D.E. Knuth, and O. Patashnik, "Concrete Mathematics", 1988, chapter 1.
It is easy to show that
$$\sum_{1 \...
- 5,362
13
votes
5
answers
1k
views
Packing obtuse vectors in $\mathbb{R}^d$
I came across this attractive theorem:
Theorem. In $\mathbb{R}^d$, there can be at most $d+1$ vectors that
form an obtuse angle with one another.
This was proved1 as a corollary of a lemma about ...
- 149k
7
votes
3
answers
2k
views
Packing density of randomly deposited circles on a plane
Let's say that I have a rectangular two-dimensional surface of bounded dimensions, $[0,A]$ and $[0,B]$:
Under "no overlap" constraints, I sequentially deposit circles of radii $r_c$ on this surface,...
- 309
35
votes
3
answers
2k
views
The kissing number of a square, cube, hypercube?
How many nonoverlapping unit squares can (nonoverlappingly) touch one unit square?
By "nonoverlapping" I mean: not sharing an interior point.
By "touch" I mean: sharing a boundary point.
&...
- 149k
26
votes
3
answers
4k
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 $\...
- 2,756
16
votes
5
answers
706
views
The smallest disk containing all sides of an $n$-gon
Start with a regular $n$-gon of side 1 and consider its sides as open segments that can be moved around in the plane, allowing only translations. Two segments may not intersect.
What is the radius ...
- 13.2k
13
votes
0
answers
660
views
Covering number estimates for Hölder balls
Let $\alpha \in (0,1]$, $r>0$ and $L>0$, and positive intwgers $n$ and $m$. The Arzela-Ascoli Theorem guarantees that the set $X(\alpha,L,r)$ of $f:[-1,1]^n\rightarrow [-r,r]^m$ with $\alpha$-...
- 4,969
13
votes
2
answers
1k
views
Average degree of contact graph for balls in a box
Imagine you dump congruent, hard, frictionless balls in a box,
letting gravity compress the balls into a stable configuration
(I believe such configurations are called
jammed.)
Assume the box ...
- 149k
8
votes
2
answers
1k
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 ...
- 6,726
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,677
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 ...
- 5,493
21
votes
1
answer
2k
views
Coiling Rope in a Box
What is the longest rope length L of radius r that can fit into a box?
The rope is a smooth curve with a tubular
neighborhood of radius r, such that the rope does not
self-penetrate. For an open ...
- 149k
16
votes
1
answer
798
views
Blocking visibility with cylinders
Suppose you have a supply of infinite-length, opaque, unit-radius cylinders,
and you would like to block all visibility from a point
$p \in \mathbb{R}^3$ to infinity with as few cylinders as possible.
...
12
votes
3
answers
2k
views
Equitably distributed curve on a sphere
Let $\gamma=\gamma(L)$ be a
simple (non-self-intersecting) closed curve of length $L$
on the unit-radius sphere $S$.
So if $L=2\pi$, $\gamma$ could be a great circle.
I am seeking the most equitably ...
- 149k
9
votes
1
answer
277
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 ...
- 149k
7
votes
1
answer
406
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 ...
- 1,721
5
votes
1
answer
246
views
5
votes
1
answer
511
views
Cover of a n-simplex with balls
Consider a n-simplex. For each edge (i,j), consider a n-ball, such that vertices i and j are antipodal on this ball. Is the simplex covered by the union of these balls? Thank you.
- 195
4
votes
0
answers
849
views
Packing space by cones: Translates best?
Let $C$ be a right circular cone, the convex hull of a unit-radius disk
and a point directly above the disk center at height $h$.
Is the ...
- 149k
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 ...
- 1,677
4
votes
2
answers
289
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 ...
- 5,493
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, ...
- 851
3
votes
3
answers
1k
views
bracketing number vs covering number
Just want to double check if the lemma on page 9 of this slides is correct:
http://www.math.leidenuniv.nl/~avdvaart/talks/09hilversum.pdf
Lemma: $N(\epsilon,\cal F,||\cdot||)\leq N_{[]}(2\epsilon,\cal ...
- 90
3
votes
1
answer
182
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 }[...
- 75
3
votes
1
answer
267
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 ...
user88381
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 ...
- 851
2
votes
1
answer
1k
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 ...
- 2,146
2
votes
0
answers
103
views
A Variant of the Malfatti Problem
See the Wikipedia entry on 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 method ...
- 5,493
2
votes
1
answer
2k
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?
- 123
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 ...
- 1,119
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 ...
- 329