Questions tagged [packing-and-covering]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
1 answer
95 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 ...
B-S's user avatar
  • 39
0 votes
0 answers
25 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$) ...
William's user avatar
0 votes
0 answers
9 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 ...
Ayoubayjx's user avatar
  • 159
1 vote
0 answers
135 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 ...
Marco Ripà's user avatar
  • 1,102
2 votes
1 answer
187 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 &...
Erel Segal-Halevi's user avatar
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 ...
Philipp Strasberg's user avatar
11 votes
1 answer
387 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?
trionyx's user avatar
  • 111
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 (...
Nandakumar R's user avatar
  • 5,401
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 ...
Nandakumar R's user avatar
  • 5,401
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 ...
Nandakumar R's user avatar
  • 5,401
1 vote
0 answers
130 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 ...
Nandakumar R's user avatar
  • 5,401
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. ...
EdvinW's user avatar
  • 121
1 vote
1 answer
59 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 ...
tony's user avatar
  • 349
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 $...
tony's user avatar
  • 349
0 votes
1 answer
112 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 ...
tony's user avatar
  • 349
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 ...
Dan's user avatar
  • 2,341
0 votes
0 answers
324 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)}...
dc3506's user avatar
  • 71
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 $...
Drew Brady's user avatar
0 votes
1 answer
150 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 ...
Jackson's user avatar
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, ...
Akira's user avatar
  • 749
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, ...
Akira's user avatar
  • 749
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 ...
Akira's user avatar
  • 749
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 ...
Manfred Weis's user avatar
  • 12.6k
2 votes
1 answer
140 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 ...
Another Grad student's user avatar
1 vote
0 answers
25 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 ...
Andres Fielbaum's user avatar
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,...
Erel Segal-Halevi's user avatar
3 votes
0 answers
124 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 ...
Ali's user avatar
  • 117
2 votes
0 answers
234 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 ...
Oscar Lanzi's user avatar
  • 1,603
5 votes
1 answer
199 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 ...
Nandakumar R's user avatar
  • 5,401
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; ...
Manfred Weis's user avatar
  • 12.6k
6 votes
1 answer
374 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 ...
Peter Koepernik's user avatar
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 ...
Penelope Benenati's user avatar
7 votes
1 answer
172 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$. ...
Penelope Benenati's user avatar
1 vote
1 answer
127 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 ...
ABIM's user avatar
  • 4,989
1 vote
1 answer
421 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}+\...
XYZ's user avatar
  • 79
2 votes
0 answers
156 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 $|...
De vinci's user avatar
  • 329
2 votes
0 answers
231 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 ...
masala's user avatar
  • 93
1 vote
0 answers
327 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 $\...
samuel's user avatar
  • 11
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 ...
Nandakumar R's user avatar
  • 5,401
1 vote
1 answer
213 views

For $x_1,...,x_n$ iid random on sphere of radius $\sqrt{d}$ in $R^d$, what is a good upper-bound on min distance of $x_{n}$ from the other $x_i$'s?

Let $n$ and $d$ be large positive integers with $n \le d^\gamma$, for some absolute constant $\gamma>0$; i.e., $n$ is at most polynomial in $d$. Let $x_1,\ldots,x_n,x_{n+1}$ be drawn iid from the ...
dohmatob's user avatar
  • 6,706
1 vote
0 answers
48 views

Which pentagon gives least packing density?

We extend Which convex pentagon gives least packing density? by going from convex pentagons to general ones. Question: Which pentagon gives the least packing density on the Euclidean plane? Note: All ...
Nandakumar R's user avatar
  • 5,401
3 votes
0 answers
134 views

Covering number $C^k$-balls in $C(\mathbb{R}^n)$

Fix a positive integer $n$ and and an non-negative integer $k$. The Arzela-Ascoli theorem guarantees that for a given positive integer $k$ and a given $L>0$ the set $$ Ball_{C^{k,1}([0,1]^n)}(0,L) ...
ABIM's user avatar
  • 4,989
3 votes
1 answer
175 views

On the thinnest cover of the plane by a given planar convex region

Is the following claim valid? Claim: Given any planar convex region C, the thinnest cover of the plane with copies of C cannot have any region where more than 2 copies overlap. In general, the ...
Nandakumar R's user avatar
  • 5,401
1 vote
0 answers
92 views

Lower bound estimate for the sum $\sum \text{diam}(U)^d$ over all countable covers of a cube

This question is inspired from the definition of Hausdorff measure. Let $C$ be a closed unit hypercube in $\mathbb R^d$ (side length equal to one, including boundary. The cube itself is at top ...
No One's user avatar
  • 1,545
2 votes
0 answers
89 views

Can Chang and Wang's proof of Thue’s Theorem on circular packing be extended into other dimentions?

The simplicity of Chang and Wang's proof of Thue’s Theorem (link on arxiv) on circular packing took me by surprise. Have similar ideas been found helpful in other dimensions? For example, partition ...
Ye Tian's user avatar
  • 161
0 votes
0 answers
69 views

packing numbers of the unit balls in Euclidean spaces and the dimensions

Let $k$, $m$ and $n$ be positive integers. Let $r$ be a positive real number. The $n$-th ordered $r$-disk configuration space on the Euclidean space $\mathbb{R}^{mk}$ is $$ F_r(\mathbb{R}^{mk},...
Shiquan Ren's user avatar
  • 1,970
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 ...
Shiquan Ren's user avatar
  • 1,970
2 votes
0 answers
187 views

Covering number bound for the Sobolev space $W^{1,1}(E)$, with $E \subset \mathbb{R}^n$

Let $E \subset \mathbb{R}^n$ have finite diameter $D(E)= \sup_{x,x' \in E}\Vert x-x' \Vert_n$. Let $W^{1,1}(E)$ denote the class of functions $f$ on $E$ admitting integrable first order weak ...
Jack London's user avatar
1 vote
1 answer
309 views

Covering number in the space of symmetric matrices

Let $S_n(\mathbb{R})$ be the set of symmetric matrices of size $n \times n$. Note $\|\Theta\|_{0}$ the number of nonzero elements of a matrix $\Theta$ and $\|\cdot\|_F$ the Froebenius norm. Consider ...
Titouan Vayer's user avatar
1 vote
0 answers
2k views

How to fill a rectangle with smaller rectangles of given sizes?

I have a problem. I try to find an algorithm to fill up a given rectangle with smaller ones. Something like in this picture: I know the size of the big rectangle, the size of all the little ...
Chuck's user avatar
  • 11