All Questions
Tagged with packing-and-covering discrete-geometry
70 questions
1
vote
1
answer
130
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
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
5
votes
1
answer
269
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 ...
- 53
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 ...
- 5,979
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?
- 111
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 ...
- 5,979
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 ...
- 5,979
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
1
vote
0
answers
19
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 ...
- 13.2k
5
votes
1
answer
230
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 ...
- 5,979
4
votes
0
answers
144
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 ...
- 1,677
2
votes
1
answer
151
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 ...
- 5,979
1
vote
0
answers
50
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 ...
- 5,979
3
votes
1
answer
177
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 ...
- 5,979
0
votes
0
answers
87
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},...
- 1,990
2
votes
1
answer
164
views
Packing densities of non-centrally symmetric planar convex regions
Reference: https://en.wikipedia.org/wiki/Smoothed_octagon
Background: The smoothed octagon is conjectured to have the lowest maximum packing density of the plane of all centrally symmetric convex ...
- 5,979
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 ...
- 5,979
4
votes
2
answers
312
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 ...
- 5,979
1
vote
3
answers
146
views
On packing axisymmetric bodies in 3D
Consider any 3D body with an axis of rotational symmetry (e.g. cone, cylinder...) and packing the 3d space efficiently with infinitely many copies of this body. Is the following claim valid?
Claim: ...
- 5,979
3
votes
1
answer
171
views
Covering radius of a lattice from relevant vectors
Let $L$ be an $n-$dimensional lattice. The Voronoi region of $L$ is given by
$$
\mathcal{V}(L)=\big\{x\in\mathbb{R}^n~|~ \|x\|_2\leq \|x-v\|_2~\forall v\in L\setminus\{0\}\big\}.
$$
Considering the ...
- 33
2
votes
0
answers
125
views
Bound on covering number for overparametrized manifold
I am trying to wrap my head around the following problem:
I have $p$ real parameters $\boldsymbol{\theta} \in \Theta = [0, 2\pi)^p$ that parametrize functions $f(\boldsymbol{\theta}) \in f(\Theta)$ ...
2
votes
4
answers
426
views
Can we almost cover any shape in the plane by disjoint/tangent disks of prescribed radii?
This is a cross-post.
Let $(a_n)_{n \in \mathbb{Z}}$ be some given, strictly increasing sequence of positive numbers, such that $\lim_{n \to -\infty} a_n=0,\lim_{n \to +\infty} a_n=+\infty$.
Let $\...
- 6,741
0
votes
0
answers
90
views
On Covering a Planar Region with Copies of a Tile of Different Shape
Background: Consider trying to cover the largest possible scaled copy of a planar region $C$ with specified shape with n instances of a tile $T$ of specified shape and size. Several families of this ...
- 5,979
4
votes
1
answer
243
views
Does there exist a scale invariant random packing of circles in the plane?
I want to construct a scale invariant random packing of the plane with circles.
Here is a way to construct a rotationally invariant, but not scale invariant random packing of the plane with circles:
...
- 1,054
22
votes
1
answer
886
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 ...
- 124
7
votes
1
answer
1k
views
Elementary precise estimate of the covering number of euclidean balls by hypercubes
I am looking for a straightforward way to upper bound the covering number of a $d$-dimensional euclidean ball by $\ell_\infty$-balls of radius $\varepsilon$, which I will call cubes of sidelength $2\...
- 172
2
votes
0
answers
131
views
Optimal way to group points in the plane into clusters
Consider a strictly decreasing sequence $d = (d_k)_{k\ge 1}$ of distances in $(0,1)$. Given a constant $C>2$, we say that $d$ has the $C$-grouping property if any finite non-empty subset $S$ (of ...
- 1,761
2
votes
2
answers
279
views
Combinatorial optimization problem with interdependent constraints on points in $[0,1]$
We are given a set $S$ of $n$ real numbers in $[0,1]$, with $0,1\in S$, and a value $\alpha\in(0,1/2)$. For each ordered triplet $(i,j,k)$ of values contained in $S$ (with $i\le j \le k$), we define ...
- 1,677
5
votes
1
answer
114
views
Packing in uniform domains
Given $N$ points $X:=(x_i)_{i \in \{1,..,N\}}$, we now define a score function $S:X \rightarrow \mathbb{N}$ that is $S(X)= \sum_{i=1}^N S(x_i)$ where the score of $S(x_i)$ is
$$S(x_i) = 2* \vert \{x_j;...
- 536
5
votes
0
answers
313
views
Trade-off between covering number, ball radius and diameter of $d$-dimensional shapes
Given any $d$-dimensional shape $X$ in the Euclidean space, let $\ell(X)$ be the length of the longest line segment connecting two points of $X$. How can we prove the following statement?
There exists ...
- 1,677
3
votes
0
answers
134
views
Two questions on counterexamples to Borsuk's conjecture and ball-packings
In 1933 Karol Borsuk conjectured the following
Can every bounded subset $E$ of $\mathbb{R}^d$ be partitioned into $(d+1)$ sets, each of which has a smaller diameter than $E$?
Whilst new to this ...
- 31
5
votes
0
answers
199
views
Existence of a honeycomb composed by nearly-hyperspherical $d$-dimensional cells having the same shape and size
Let $\mathcal{H}$ the class of all honeycombs composed by $d$-dimensional cells $C$ having all the same shape and size in a $d$-dimensional space $\mathcal{S}$.
Let $s(C)$ and $\ell(C)$ be ...
- 1,677
1
vote
1
answer
138
views
Packing L's in Tans and L's in L's
I'm a young researcher and I'm pretty new in this field. I want to work on packing problem "L's in Tans" and "L's in L's" as presented on https://erich-friedman.github.io/packing ....
- 121
3
votes
0
answers
184
views
Fitting $\frac1n\times\frac1{n+1}$ rectangles into the unit square [duplicate]
Consider the set of rectangles $r_n | n \in \Bbb N$ such that rectangle $r_n$ has shape $\frac1n\times\frac1{n+1}$. The total area composed by one copy of each $r_n$ as $n$ ranges from $1$ to ...
- 1,247
26
votes
0
answers
359
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$ ...
- 151k
7
votes
0
answers
44
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 ...
- 23.2k
1
vote
0
answers
103
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 ...
- 71
6
votes
0
answers
1k
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 $...
- 13.4k
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 ...
- 19.7k
1
vote
0
answers
278
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\}$ ...
- 733
9
votes
2
answers
470
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 ...
- 7,276
11
votes
2
answers
455
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}...
- 151k
3
votes
1
answer
186
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 }[...
- 75
1
vote
0
answers
71
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 ...
- 579
2
votes
0
answers
87
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 $\...
- 231
9
votes
1
answer
274
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 $...
- 19.7k
1
vote
0
answers
124
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) ...
- 13.4k
16
votes
5
answers
712
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 ...
- 13.4k
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 ...
- 151k