Questions tagged [packing-and-covering]
The packing-and-covering tag has no usage guidance.
213 questions
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
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
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 ...
- 506
7
votes
1
answer
117
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 ...
- 506
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 ...
CommunityBot
- 1
9
votes
1
answer
442
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 ...
CommunityBot
- 1
0
votes
1
answer
79
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; ...
CommunityBot
- 1
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
1
vote
1
answer
66
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 ...
CommunityBot
- 1
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 ...
- 6,367
5
votes
0
answers
187
views
Packing cylinders in a sphere: Phase transition?
Let $S$ be a unit-radius sphere in $\mathbb{R}^3$,
and $c$ a cylinder of length $L$ and radius $r<2$.
It appears to me that for $L \in [\sqrt{2},2]$
and "small" $r$,
the optimal packing ...
- 151k
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
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 ...
CommunityBot
- 1
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
3
votes
1
answer
406
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 &...
- 5,409
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$. ...
- 5,382
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 ...
- 2,858
2
votes
1
answer
162
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 ...
- 405
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 ...
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
2
votes
2
answers
273
views
Number of edge-disjoint cycles in a holey graph
Let $\Gamma$ be a connected graph with $H^1(\Gamma) \cong \mathbb{Z}^d$. Can we give a lower bound (preferably of the form $\gg d$) on the maximal number of edge-disjoint cycles one can find in $\...
- 32.1k
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
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 ...
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
3
votes
1
answer
248
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 ...
- 980
11
votes
1
answer
403
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?
- 151k
2
votes
0
answers
84
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 ...
- 4,713
1
vote
1
answer
63
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 ...
- 128k
2
votes
0
answers
106
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 ...
- 6,367
1
vote
0
answers
137
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 ...
- 5,979
2
votes
1
answer
105
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. ...
- 121
0
votes
1
answer
92
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 ...
- 128k
0
votes
2
answers
118
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 $...
- 405
13
votes
0
answers
818
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$-...
- 5,405
0
votes
1
answer
148
views
packing numbers and configuration spaces of the torus
Let $S^1$ be the unit circle of radius $1$.
For any $k\geq 1$, let the $k$-dimensional torus $T^k= \underbrace{S^1\times S^1\times\cdots\times S^1}_k$ be the $k$-fold self-Cartesian ...
- 1,085
3
votes
0
answers
328
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 ...
- 2,370
0
votes
1
answer
182
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 ...
- 1
3
votes
0
answers
144
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 ...
- 9,501
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,...
- 1,446
13
votes
2
answers
3k
views
How many vertices/edges/faces at most for a convex polyhedron that tiles space?
I wonder if this problem has already been examined before:
Consider a convex polyhedron that tiles $\mathbb R^3$. What is the maximum of vertices/edges/faces that such a polyhedron can have?
...
- 2,821
3
votes
1
answer
132
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, ...
- 45k
3
votes
3
answers
2k
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 ...
- 11
5
votes
1
answer
230
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,549
2
votes
1
answer
139
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, ...
- 109k
2
votes
1
answer
259
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 ...
- 835