Questions tagged [packing-and-covering]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
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 \...
Kaveh's user avatar
  • 5,362
60 votes
4 answers
5k views

Is there a mathematical and information theoretic 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 with ...
Turbo's user avatar
  • 13.7k
35 votes
3 answers
2k views

The kissing number of a square, cube, hypercube?

How many nonoverlapping unit squares can (nonoverlappingly) touch one unit square? By "nonoverlapping" I mean: not sharing an interior point. By "touch" I mean: sharing a boundary point.   &...
Joseph O'Rourke's user avatar
35 votes
1 answer
768 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 ...
Yoav Kallus's user avatar
  • 5,926
27 votes
2 answers
877 views

Careless packing

The sequence $\frac{1}{2}, \frac{1}{2\cdot 2}, \frac{1}{3\cdot 4}, \frac{1}{4\cdot 6}, \frac{1}{5\cdot 8}, \frac{1}{6\cdot 10},\ldots$ has a curious property, as follows: a) the series with these ...
David Feldman's user avatar
26 votes
3 answers
4k 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 $\...
Robin Houston's user avatar
25 votes
0 answers
343 views

Can 4-space be partitioned into Klein bottles?

It is known that $\mathbb{R}^3$ can be partitioned into disjoint circles, or into disjoint unit circles, or into congruent copies of a real-analytic curve (Is it possible to partition $\mathbb R^3$ ...
Joseph O'Rourke's user avatar
22 votes
1 answer
880 views

Happy ants never leave compact domain?

I am curious if the following seemingly simple question has an easy answer? Consider an ant population of $N$ ants that lives in $\mathbb R^2$. Each ant can be labeled by some coordinate $x\in \mathbb ...
Pritam Bemis's user avatar
22 votes
0 answers
377 views

What is the covering density of a very thin annulus? Is it $\frac{\pi\sqrt{51\sqrt{17}-107}}{16}$?

Take some very small $\epsilon>0$, and consider the annulus/ring given by the set $\{(r,\theta)\ |\ 1-\epsilon\le r\le1\}\subset \mathbb{R}^2$. We wish to place translated copies of this annulus ...
RavenclawPrefect's user avatar
21 votes
1 answer
2k views

Coiling Rope in a Box

What is the longest rope length L of radius r that can fit into a box? The rope is a smooth curve with a tubular neighborhood of radius r, such that the rope does not self-penetrate. For an open ...
Joseph O'Rourke's user avatar
20 votes
1 answer
3k views

A circle packing conjecture

Consider $n$ circles with variable radii $r_1,\ldots, r_n$ that pack inside a fixed circle of unit radius. In other words, all $n$ variable-radius circles are contained in the unit radius circle and ...
Veit Elser's user avatar
  • 1,045
20 votes
3 answers
3k views

How many unit squares can you pack into a rectangle with nearly integer side lengths?

Earlier today, somebody asked what looks like a homework problem, but admits the following reading which I think is interesting: Suppose $a_1,\dots, a_n$ are positive integers, and $\varepsilon$ is ...
Anton Geraschenko's user avatar
19 votes
2 answers
908 views

What is the largest possible thirteenth kissing sphere?

It is well-known that it is impossible to arrange 13 spheres of unit radius all tangent to another unit sphere without their interiors intersecting. This was apparently the subject of disagreement ...
Jamie J. Taylor's user avatar
18 votes
4 answers
1k views

Pennies on a carpet problem

I recently read the following "open problem" titled "Pennies on a carpet" in "An Introduction To Probability and Random Processes" by Baclawski and Rota (page viii of book, page 10 of following pdf),...
Alex R.'s user avatar
  • 4,902
16 votes
5 answers
704 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 ...
Wolfgang's user avatar
  • 13.2k
16 votes
1 answer
798 views

Blocking visibility with cylinders

Suppose you have a supply of infinite-length, opaque, unit-radius cylinders, and you would like to block all visibility from a point $p \in \mathbb{R}^3$ to infinity with as few cylinders as possible. ...
13 votes
5 answers
1k 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 ...
Joseph O'Rourke's user avatar
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? ...
Wolfgang's user avatar
  • 13.2k
13 votes
1 answer
3k views

Is there a version of König's theorem for tripartite 3-graphs?

I would like to know if there exists a version of König's theorem for tripartite $3$-graphs. In other words, let $G = (V,T)$ be a tripartite $3$-graph. That is, $V$ is a set of vertices (with $V$ ...
tbg's user avatar
  • 131
13 votes
2 answers
1k views

Average degree of contact graph for balls in a box

Imagine you dump congruent, hard, frictionless balls in a box, letting gravity compress the balls into a stable configuration (I believe such configurations are called jammed.) Assume the box ...
Joseph O'Rourke's user avatar
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$-...
ABIM's user avatar
  • 5,019
13 votes
0 answers
733 views

$\epsilon$-nets with respect to the cut norm

The cut norm $||A||\_C$ of a real matrix $A = (a_{i,j}) \in \mathcal{R}^{n\times n}$ is the maximum over all $I \subseteq [n], J \subseteq [n]$ of the quantity $\left|\sum_{i \in I, j \in J}a_{i,j}\...
Aaron's user avatar
  • 794
12 votes
3 answers
2k 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 ...
Joseph O'Rourke's user avatar
12 votes
1 answer
1k views

Cobounded ⇒ cocompact?

Assume $\Gamma$ acts by isometries on a separable Hilbert space $H$, and $$\operatorname{diam} H/\Gamma\le 1.$$ Is it true that $H/\Gamma$ is compact? Stupid example. Assume the action of $\...
Anton Petrunin's user avatar
11 votes
4 answers
446 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 ...
Yoav Kallus's user avatar
  • 5,926
11 votes
2 answers
447 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}...
Joseph O'Rourke's user avatar
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?
trionyx's user avatar
  • 111
11 votes
0 answers
213 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 "...
Joseph O'Rourke's user avatar
10 votes
4 answers
620 views

Packing and isoperimetrics

Suppose a manufacturer bottles small units of liquid and ships them via very large trucks. If the transportation cost nothing, spherical bottles would minimize the packaging cost (isoperimetric ...
David Feldman's user avatar
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 $...
Sam Nead's user avatar
  • 26k
10 votes
1 answer
488 views

Packing regular tetrahedra of edge length 1 with a vertex at the origin in a unit sphere

Consider the following problem: How many regular tetrahedra of edge length 1 can be packed inside a unit sphere with each one has a vertex located at the origin? The answer is at least 20, forming ...
YuiTo Cheng's user avatar
10 votes
1 answer
545 views

Are packing-homogeneous spaces homogeneous?

Given a metric space (M,d) define the packing function P(x,R,r) to be the maximum number of non-intersecting balls of radius r with centers in the ball B(x,R). Let’s call M packing-homogeneous if the ...
Yevgeny Liokumovich's user avatar
10 votes
0 answers
493 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-...
Morteza Azad's user avatar
10 votes
0 answers
492 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 question ...
Erel Segal-Halevi's user avatar
9 votes
3 answers
519 views

Mutually tangent ellipsoids in 3 space

I recently heard a claim that for any n, it is possible to arrange n ellipsoids in 3 space such that each pair of ellipsoids is kissing. Is this true, and if so, how? Edit: By kissing, I mean that I ...
Linda Brown Westrick's user avatar
9 votes
2 answers
8k 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 ...
Raymond Hemmecke's user avatar
9 votes
2 answers
422 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 ...
Wlodek Kuperberg's user avatar
9 votes
1 answer
276 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 ...
Joseph O'Rourke's user avatar
9 votes
1 answer
200 views

Which unimodular lattices $L\subset \mathbb R^2$ minimize $f_t(L):=\sum_{ v\in L} e^{-t \|v\|_2}$? (for parameters $t>0$)

$\DeclareMathOperator\SL{SL}\DeclareMathOperator\SO{SO}$Consider the lattices in $\SL(2,\mathbb R)(\mathbb Z^2)$ up to rotation. The space of such lattices can be identified with the modular surface $\...
user84899's user avatar
  • 241
9 votes
1 answer
267 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 $...
James Propp's user avatar
  • 19.4k
9 votes
1 answer
652 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 ...
Victor Wang's user avatar
9 votes
0 answers
248 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," ...
Joseph O'Rourke's user avatar
9 votes
0 answers
171 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 ...
pgadey's user avatar
  • 585
9 votes
0 answers
192 views

Asymptotics of packing

Define $m(n,k,l)$ as the maximal size of a family $k$-element subsets of $[n]$ having the property that the intersection of every two sets is less than $l$. As stated on wikipedia, in 1985 Rödl ...
Manu's user avatar
  • 351
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
8 votes
1 answer
678 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 $...
Christopher's user avatar
8 votes
1 answer
691 views

Upper bound for tetrahedron packing?

There have been several recent advances on packing regular tetrahedra in $\mathbb{R}^3$. All the results I've seen have been lower bounds -- first John Conway and Sal Torquato showed that there ...
Matthew Kahle's user avatar
8 votes
2 answers
1k 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 ...
dohmatob's user avatar
  • 6,716
8 votes
1 answer
217 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 ...
Yoav Kallus's user avatar
  • 5,926
8 votes
2 answers
563 views

Coiling Rope in a Box: Decidable?

Is the problem Coiling Rope in a Box decidable? To be specific, is this decidable? Given $L > 0$ and $r \in (0,\frac{1}{2})$, both rational, can a rope of length $L$ and radius $r$ fit ...
Joseph O'Rourke's user avatar

1
2 3 4 5