Questions tagged [packing-and-covering]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
1 answer
99 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 ...
8 votes
1 answer
359 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 ...
0 votes
1 answer
66 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; ...
0 votes
0 answers
26 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$) ...
2 votes
2 answers
232 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 $\...
0 votes
0 answers
10 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 ...
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
138 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 ...
2 votes
1 answer
143 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 ...
2 votes
1 answer
189 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 &...
11 votes
1 answer
388 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?
0 votes
0 answers
45 views

Optimal packing and covering of a triangle with squares

We continue from Another variant of the Malfatti problem. Given a triangle T and a number n, how to cover it with n squares (of possibly different dimensions) such that the sum of the areas (...
2 votes
0 answers
76 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 ...
1 vote
1 answer
62 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 ...
2 votes
0 answers
102 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 ...
1 vote
0 answers
131 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 ...
2 votes
1 answer
94 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. ...
1 vote
1 answer
61 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 ...
1 vote
2 answers
99 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 $...
0 votes
1 answer
114 views

Lipschitz maximal inequality for random process

I am confused on the Lemma 5.7 (Lipschitz maximal inequality) here. Let me first restate the definition and the lemma: Def $\{X_t\}_{t\in T}$ is called Lipschitz for metric $d$ on $T$ if there exists ...
13 votes
0 answers
638 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$-...
0 votes
0 answers
338 views

Upper bound of covering number of $\ell_1$-ball under $\ell_2$-norm

Let $B^n_1 = \{x : \Vert x\Vert_1 ≤ 1\}$ be the $\ell_1$-norm unit ball. How can we prove the covering of $B^n_1$ under $\Vert\cdot\Vert_2$ satisfies $$\sqrt{\log N(B^n_1, \Vert\cdot\Vert_2, \epsilon)}...
0 votes
1 answer
138 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 ...
0 votes
0 answers
75 views

When do covering and packing have the same behavior: when does $\log N_p(\delta) \lesssim \log N_c(\delta)$ for all $\delta > 0$ hold?

Let $X \equiv (X, d)$ denote a compact metric space and let $N_c(\delta), N_p(\delta)$ denote the covering and packing numbers of space, respectively. Here $\delta > 0$. Evidently we always have $...
2 votes
0 answers
237 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 ...
0 votes
1 answer
151 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 ...
3 votes
0 answers
125 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 ...
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,...
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? ...
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, ...
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 ...
5 votes
1 answer
200 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,...
2 votes
1 answer
130 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, ...
2 votes
1 answer
225 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 ...
4 votes
2 answers
449 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
0 answers
18 views

Regular covering of planar pointsets with convex polygons

Question: What is known about the problem of covering a finite set of $\mathbb{P}$ of points in the plane with convex polygons that have the same number $m$ of points from $\mathbb{P}$ as corners and ...
10 votes
2 answers
859 views

Packing twelve spherical caps to maximize tangencies

Suppose that $v_i$, for $i \in \{1, 2, \ldots 11, 12\}$, are twelve unit length vectors based at the origin in $R^3$. Suppose that $|v_i - v_j| \geq 1$ for all $i \neq j$. What arrangement of the $...
1 vote
1 answer
128 views

Packing number in finite-dimensional normed spaces

I am working on a paper and quoted the following result from these lecture notes. Where can I find a reference to this result either in a book or a paper, that I can cite? (I looked on the course ...
1 vote
0 answers
26 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 ...
5 votes
1 answer
201 views

Which pyramids fill space?

Let us define a pyramid as a convex polyhedron with one quadrilateral face and four triangular faces. Question: How many pyramids (or families of pyramids) are known that can fill 3D space without ...
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 ...
6 votes
1 answer
376 views

Does finite Hausdorff dimension imply finite packing dimension?

In other words, does there exist a metric space $(E,\rho)$ with finite Hausdorff dimension but infinite packing dimension? Here are my thoughts: I know that it is generally hard to relate Hausdorff ...
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 ...
7 votes
1 answer
173 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 vote
1 answer
433 views

Covering numbers for products of functions from two spaces?

Exercise (HW1): Let $\mathcal{F}$ and $\mathcal{G}$ be classes of measurable function. Then for any probability measure $Q$ and any $1 \leq r \leq \infty$, (i) $N_{[]}\left(2 \epsilon, \mathcal{F}+\...
2 votes
0 answers
160 views

Sudakov's lower bound type inequality for supremum of Chi-squared random variables

Let $\varepsilon$ be $n$-dimensional standard Gaussian veector, i.e., $\varepsilon \sim N_n(0, I_n)$. Let $\mathcal{P}$ be a subset of symmetric projection matrices in $\mathbb{R}^{n \times n}$ with $|...
2 votes
0 answers
235 views

Covering/Bracketing number of monotone functions on $\mathbb{R}$ with uniformly bounded derivatives

I am interested in the $\| \cdot \|_{\infty}$-norm bracketing number or covering number of some collection of distribution functions on $\mathbb{R}$. Let $\mathcal{F}$ consist of all distribution ...
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 \...
1 vote
0 answers
328 views

Bound on covering number of Lipschitz functions – missing part in proofs of Kolmogorov et al

Given a metric space $(\mathcal{X},\rho)$ and $\mathcal{A}\subset\mathcal{X}$ totally bounded, i.e. $\mathcal{A}$ has a finite $\varepsilon$-covering for any $\varepsilon>0$. Consider $\...
2 votes
1 answer
148 views

On rigid packings of the plane with a constraint

This post continues Thinnest rigid packings of the plane A packing of the plane with copies of any shape is called rigid (or "stable") if every unit is fixed by its neighbors, i.e., no unit ...