Questions tagged [packing-and-covering]
The packing-and-covering tag has no usage guidance.
20 questions from the last 365 days
1
vote
1
answer
129
views
Packing problems where parts of objects are allowed to intersect
I'm interested in packing problems where the objects are allowed to intersect.
For a simple example, consider stacking 1×2 tiles on a nxn chessboard. Each 1×2 tiles consists of part X and Y (both 1×1)....
- 11
1
vote
0
answers
37
views
Metric entropy of an ellipsoid
Let $B^d_2$ denote the unit ball of $\ell_2^d$ and let $T$ be an invertible linear map.
Consider the function
$$
H(T) := \log M(TB_2^d, B_2^d),
$$
which is the packing entropy for $TB_2^d$ by $B_2^d$....
- 380
2
votes
1
answer
156
views
Question about coverings of zero Hausdorff measure compact sets
Consider a compact set $E\subset \mathbb{R}^n$ ad assume that ${\cal H}^{n-1}(E)=0$.
If $\epsilon>0$, there is a finite covering of $E$ made of $N_\epsilon$ open balls $B_{r_{\epsilon,k}}(x_{\...
- 205
0
votes
0
answers
29
views
Stable gap-less packing of a box with boxes
define a box packing as gap-less if
all inner boxes have disjoint interior
the sum of volumes of the inner box equals that of the outer box
the sum of the extents of the inner boxes in each principal ...
- 13.2k
4
votes
1
answer
97
views
Inner regularity property of covering number of metric spaces
Let $(X,d)$ be a complete metric space and $n\in\mathbb N$. Suppose that every finite subset $F\subset X$ can be covered by $n$ closed balls of $X$ (that is, $N(Y,d,1)\le n$, in terms of covering ...
- 60.5k
2
votes
0
answers
48
views
Maximum coverage of an orthogonal polygon using $k$ rectangles
I have an orthogonal polygon (all edges are horizontal or vertical) which is convex (no holes in any row of column of the polygon).
I would like to cover as much as possible of this orthogonal polygon ...
- 21
4
votes
0
answers
66
views
Show that there are infinitely many well-separated grids from a fixed set of points
I have stumbled upon a question which naturally arises when trying to bin a set of $n$ points into equispaced bins such that they are sufficiently well separated from the bin edges.
Take $n$ points $...
8
votes
0
answers
149
views
Do the $\ell^{\infty}$ and $\ell^1$ norms yield minimal doubling constants amongst all norms on $\mathbb{R}^n$?
Setting:
Let $X:=\mathbb{R}^n$ for some positive integer $n$. For each $1\le p\le \infty$ let $d_p$ denote the metric induced by the $\ell^p_n$ norm thereon.
Note that, the doubling constant of a ...
- 5,405
0
votes
0
answers
65
views
Random covering on rectangles
Let $\mathrm{Rect}$ denote the class of axis-parallel rectangles $r: \mathbb{R}^2 \to \{0,1\}$, assigning $1$ if the point is inside the rectangle and $0$ otherwise. Let $\mathcal{D}$ be a ...
- 159
0
votes
0
answers
13
views
Enumerating the directed vertex-disjoint cycle covers of digraphs
A directed cycle-cover of a digraph $D$ is in the sense of this post equivalent to a perfect matching in the related undirected biadjacency graph $B$ in which the edges connect a vertex $u$ of $D$ in ...
- 13.2k
2
votes
0
answers
336
views
Who contributed [GT13] to "Computers and Intractability"?
This is a followup to my question How does the complexity of calculating the Permanent imply the NP completeness of directed 3-cycle cover?
Question:
who contributed problem [GT13] PARTITION INTO ...
- 13.2k
12
votes
1
answer
380
views
Do lattices with small covering radius have sublattices with small covering radius?
For me a lattice is a discrete subgroup of $\mathbb R^n$. The linear span of a lattice, written $\Lambda \otimes \mathbb R$, is the $\mathbb R$-vector subspace of $\mathbb R^n$ generated by $\Lambda$. ...
- 148k
5
votes
1
answer
268
views
Is the maximal packing density of identical circles in a circle always an algebraic number?
There is a lot of interest in the maximal density of equal circle packing in a circle. And I thought that knowing whether or not the solution is always algebraic or not would be useful.
My original ...
- 53
6
votes
1
answer
413
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 ...
- 5,979
30
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 ...
- 114k
2
votes
0
answers
39
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{...
- 384
0
votes
1
answer
115
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 ...
- 39
0
votes
0
answers
38
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$) ...
- 1
0
votes
0
answers
14
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 ...
- 159
1
vote
0
answers
157
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,451