Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [packing-and-covering]

The tag has no usage guidance.

1
vote
1answer
71 views

Growth rate of bounded Lipschitz functions on compact finite-dimensional space

Let $\mathcal X$ be a metric space of diameter $D$ and "dimension" (e.g doubling dimension) $d$. Let $L \in [0, \infty]$ and $M \in [0, \infty)$ and consider the class $\mathcal H_{M,L}$ of $L$-...
4
votes
0answers
113 views

Tiling squares with oblongs

An oblong is a rectangle whose width and length are consecutive integers: 1x2, 2x3, 3x4, etc. Does N exist such that it is possible to split the first N oblongs into 2 or more non-intersecting sets so ...
7
votes
0answers
28 views

Inefficient covering by translates

While trying to answer this question, I arrived at another question: How many translates of $\{0,1\}^n$ does it take to cover $\mathbb F_3^n$? The broader context is: consider a set $S$ and a ...
1
vote
0answers
43 views

Upper bounds on $\epsilon$-covers of arbitrary compact manifolds

Let $M \subset \mathbb{R}^d$ be a compact $k$-dimensional manifold embedded in $\mathbb{R}^d$. Let $\mathcal{N}(\epsilon)$ denote the size of the minimum $\epsilon$-cover $P$ of $M$, that is for every ...
4
votes
0answers
89 views

Lower bound on $\epsilon$-covers of arbitrary manifolds

Let $M \subset \mathbb{R}^d$ be a $k$-dimensional manifold embedded in $\mathbb{R}^d$. Let $\mathcal{N}(\epsilon)$ denote the size of the minimum $\epsilon$-cover $P$ of $M$, that is for every point $...
2
votes
0answers
83 views

Covering a sphere with ellipsoid-products in high dimension

For $\Sigma\geq 0$ a $k\times k$ matrix and large $n$, fix $E:= \{(x_i)_{i=1}^n: \sum_i x_i^\dagger \Sigma x_i \leq n\}$. Fix $(z_m)_m$ as $M$ points iid uniform on $\mathbb{S}^{nk-1}\subset \mathbb{...
7
votes
3answers
383 views

Coverage of balls on random points in Euclidean space

We have n points randomly distributed in a d-dimensional unit hypercube. We randomly sample k of those points and center a ball with radius r on each of those k points. Does there exist an estimate of ...
5
votes
0answers
161 views

How to pack 27 $a\times b\times c$ blocks into a cube of side $a+b+c$ with some kind of symmetry?

Recently I stumbled on the problem quoted here about a geometric proof of the AM-GM inequality $$(a_1+\cdots+a_n)^n\ge n^n a_1\cdots a_n$$ by packing $n^n$ rectangular $ n$-dimensional boxes of sides $...
1
vote
2answers
151 views

Lower bound on misclassification rate of Lipschitz functions in terms of Lipschitz constant

Important note @MateuszKwaśnicki in the comment section has raised a fundamental issue with the current statement of the problem. I'm trying to bugfix it. Setup I wish to show that a Lipschitz ...
5
votes
2answers
191 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 ...
9
votes
0answers
432 views

Which finite sets could be packed into a square?

This question is inspired by an interesting visualization of the finite levels of von Neumann's hierarchy on Adam P. Goucher's blog, Complex Projective 4-Space. The problem starts with a two-...
2
votes
2answers
148 views

Counting triples family with double shared elements

We have a set of elements $S=\{1,2,3, . . . , N\}$ and family $F$ of $N$ triples of elements in $S$ ($N$ is a multiple of 3). Each element of $S$ appears in exactly three triples. The elements in each ...
1
vote
1answer
89 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 ...
6
votes
0answers
68 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 ...
1
vote
0answers
184 views

Sphere packings with antipodal (unequal) spheres

Let $\|\cdot\|_2$ denote the Euclidean norm, let $\langle \cdot, \cdot\rangle$ denote the standard dot product, and let $\mathcal{S}^{d-1} = \{\mathbf{x} \in \mathbb{R}^d: \|\mathbf{x}\|_2 = 1\}$ ...
5
votes
1answer
412 views

Randomly covering a sphere

Let $S$ be the $n$-dimensional unit sphere in the Euclidean space. Further, let $X_1,\ldots,X_k$ and $Y_1,\ldots,Y_m$ be iid $S$-valued random variables with common (unknown) distribution $\mu$. With $...
9
votes
2answers
208 views

Density of a saturated random packing of congruent circles

The problem of the expected density of a saturated random packing of unit circles in the plane can be described as follows. In a circular region $C$ of a large radius pick a point at random and draw ...
47
votes
4answers
4k views

Is there a mathematical explanation for this cube packing phenomenon?

I saw this unintuitive result on dice packing: A jumble of thousands of cubic dice, agitated by an oscillating rotation, can rapidly become completely ordered, a result that is hard to produce ...
11
votes
2answers
310 views

Dodecahedral rolling distance

Let a dodecahedron sit on the plane, with one face's vertices on an origin-centered unit circle. Fix the orientation so that the edge whose indices are $(1,2)$ is horizontal. For any $p \in \mathbb{R}...
2
votes
0answers
44 views

Packing net of simplex

For given $d$, we can define the simplex as follows, $S=\{(x_1,x_2,\cdots,x_d):x_1\geq x_2\geq \cdots\geq x_d\geq 0,\sum x_i=1\}$. We can define the distance on $S$ as $L_1$ distance. An $\epsilon$ ...
9
votes
1answer
191 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 ...
4
votes
1answer
160 views

Equation of state for hard rods

Some context: For ideal gases, the thermodynamic equation of state is the well-known: $$ pV = nRT \tag{1} $$ where $n$ is the amount of substance, $R$ the universal gas constant and $P,V,T$ are ...
2
votes
1answer
181 views

Packing number of $\ell_1$ ball in $\ell_{\infty}$ metric

Consider the $d$-dimensional $\ell_1$ ball $\mathbb B_d=\{x\in\mathbb R^d: \|x\|_1\leq 1\}$, where $\|x\|_1=\sum_{i=1}^d{|x_i|}$. I'm interested in the maximum size of the (finite) subset $S\subseteq\...
3
votes
1answer
153 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 }[...
27
votes
3answers
3k 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 $\...
10
votes
4answers
281 views

Sequential addition of points on a circle, optimizing asymptotic packing radius

Suppose I have to put $N$ points $x_1, x_2, \ldots, x_N$ on the circle $S^1$ of length 1 so as to achieve the largest minimum separation (packing radius). The optimal solution is the equally spaced ...
1
vote
0answers
59 views

Packing the box $[0,X^{\delta_1}] \times [0,X^{\delta_2}] \times [0,X^{\delta_3}] \subseteq \mathbb{R}^3$ with cubes

Let $0 < \delta_1 \leq \delta_2 \leq \delta_3 \leq 1$, and consider the box $B := [0,X^{\delta_1}] \times [0,X^{\delta_2}] \times [0,X^{\delta_3}] \subseteq \mathbb{R}^3$. Let $X > 3$ say. Is it ...
2
votes
1answer
169 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 ...
5
votes
3answers
331 views

Exact bin packing the harmonic series: references?

Given $n$ and $B_n= \lceil H_n \rceil$, where the latter is the $n$th harmonic number $\sum^n_{i=1} 1/i$, for most $n$ it is easy to pack the first $n$ terms of the harmonic series into $B_n$ many ...
4
votes
2answers
288 views

Minimum number of rectangles in a polygon

Given a polygon and dimension $d$, find a minimum partition of rectangles that has either of its dimensions equal to $d$. Example: Consider the following diagram: I want to cover maximum shaded ...
2
votes
0answers
71 views

lower bound for sum of (squared) distances under a minimum distance restriction

I am trying to solve a packing problem in discrete geometry and it would be useful to know the answer to the following problem. Let $A_1$, $A_2$,..., $A_n$ be $n$ points in the Euclidean plane $\...
11
votes
0answers
180 views

Electrons on a pancake ellipsoid

The problems of minimizing the potential energy of electrons on a sphere, or maximizing the smallest distance between the electrons, have been well-studied. E.g., see the earlier MO question "...
9
votes
1answer
256 views

Integer sets with forbidden differences

Given a finite set $S$ of positive integers, and a positive integer $n$, let $F(n,S)$ be the largest possible cardinality of a subset of {$1,2,\dots,n$} no two of whose elements differ by a number in $...
3
votes
2answers
126 views

Sub-sector covers for disks and balls

Define an open $k$-sector of a disk as the portion between two radii separated by an angle of $2\pi/k$, but open along the two radii (and closed along the circle boundary). Call a set a sub-$k$-sector ...
7
votes
1answer
152 views

Optimal stacking of split logs

Consider firewood logs as unit-radius cylinders of the same length. Each log is split into $k$ pieces by equiangular sectors meeting in the circle center: $k=2$ leads to semicircles, $180^\circ$; $k=3$...
1
vote
0answers
117 views

The smallest disk containing all cirular arcs

In a comment to my recent question about covering segments by a disk, Gerhard Paseman has suggested a generalisation: replacing the segments of the original $n$-gon by a simple closed (say, convex) ...
16
votes
5answers
653 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 ...
7
votes
5answers
454 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 ...
9
votes
2answers
5k views

How to pack 3D boxes into a bigger box?

Given a box of given size $L\times M\times N$ and a list of smaller boxes of given sizes $(l_i,m_i,n_i)$, decide whether the smaller boxes altogether fit into the big box (and produce such a packing ...
11
votes
2answers
1k 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 ...
9
votes
0answers
225 views

Randomly placing nonoverlapping unit cuboids

Suppose one places unit cuboids of dimension $d$ with min-corners uniformly distributed to lie in $[0,n]^d$, but with cuboid (strict) overlap forbidden. At some point, the region is "saturated," ...
35
votes
1answer
669 views

What measurable quantity can constrain the number of odors human can discriminate?

This is not a very typical MO question, but I hope you bear with me. It concerns a recent disagreement in the biology literature about how many different odors humans can discriminate. The authors of ...
2
votes
0answers
231 views

Is the kissing number in $n$ dimensions always divisible by $n$? And what is the base of exponential growth of the kissing number?

And why are the kissing numbers for 1, 2, 3, 4 and 8 dimensions all highly composite numbers?
7
votes
1answer
157 views

Translative packing constant strictly larger than lattice packing constant

Simply put, my question is this: what is the smallest dimension, if any, where we can know for sure that a convex body exists whose translative packing constant is strictly larger than its lattice ...
4
votes
0answers
467 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 ...
10
votes
1answer
531 views

Triangle (constrained number, rather than shape) packing?

Are there any interesting results on optimal packings in the plane using a fixed number of triangles (without a fixed size or shape constraint)? For instance, what's the maximum area packing of the ...
9
votes
0answers
164 views

Characterizing the norms on $\mathbb{R}^3$ coming from Platonic solids

Recall that any sufficiently nice compact centrally symmetric convex body in $B \subset \mathbb{R}^3$ gives rise to a Banach norm on $\mathbb{R}^3$ which has $B$ as its unit ball. Is there a nice ...
-2
votes
1answer
129 views

Combination of 2 × 1 × 1 cubes inside a 3 × 3 × n cube [closed]

You have a block with a width of 3, depth of 3 and a height n Given n, in how many ways can you fill this block with smaller blocks of 2 x 1 x 1? if n is uneven, one 1x1x1 block will be unused. This ...
4
votes
1answer
262 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.
7
votes
0answers
402 views

Rectangology and squareology

I thought that rectangles were simple, and squares even simpler. Until my research has led me to several questions about rectangles and squares, which I can't solve. I started by posting this ...