All Questions
Tagged with packing-and-covering discrete-geometry
70 questions
9
votes
0
answers
249
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," ...
- 151k
9
votes
1
answer
666
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 ...
- 430
5
votes
1
answer
547
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.
- 195
10
votes
0
answers
493
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 ...
- 3,549
3
votes
1
answer
305
views
Is this cube packing possible?
I know how to pack $5$ unit squares in a square of side length $2+\frac{\sqrt{2}}{2}$. Is there an $\varepsilon>0$ such that there exists a packing of $9$ unit cubes in a cube of side length $3-\...
- 7,633
2
votes
1
answer
1k
views
2d bin packing problem, with opportunity to optimize the size of the bin
I have been tasked with optimizing a manufacturing process. It is a non-trivial, NP hard problem. The problem is similar to the 2d bin packing problem, but we are trying to optimize the size of the ...
- 119
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.
&...
- 151k
9
votes
3
answers
525
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 ...
- 1,601
1
vote
2
answers
204
views
Disks Packing Variant
Usually disk packing problems require that no two disks of the packing intersect.
Does anybody know if the problem has been studied when disks may intersect but they are not allowed to contain the ...
- 57
27
votes
2
answers
891
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 ...
- 17.6k
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?
...
- 13.4k
1
vote
1
answer
227
views
Constant hole density on the area of a circle
I need to create about 100 (small) holes in a distributor plate (hole diam = 0.5 mm; plate diameter = 100 mm). The sm. holes should be distributed in such a way that the density (hole/area) is nearly ...
- 13
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 ...
- 151k
3
votes
2
answers
551
views
Torus in $\mathcal{R}^3$
Hi
I'm interested in packing the 3 space as dense as possible using equally sized tori whose major radius is much bigger than their minor radius in.
Do you have any idea how to attack this problem?
...
- 239
2
votes
1
answer
1k
views
Sphere packing in a sphere
Let $S_a^d$ be the $(d-1)$-dimensional sphere of radius $a$ in $\mathbb{R}^d$. Let $r>0$ be a constant and $R=\nu r$ where $\nu>1$ (some constant). Are there any known upper bounds on the number ...
- 3,217
5
votes
3
answers
2k
views
Optimal packing of spheres tangent to a central sphere
Please consider a central, ordinary 2-sphere $S_1$, of some radius $r_1$, and a second ordinary sphere, $S_2$, of radius $r_2$, where $r_2 \leq r_1$.
My question concerns optimal values for the ...
99
votes
7
answers
20k
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 \...
- 5,502
4
votes
7
answers
2k
views
How to generate a net on a 8-dimensional sphere
Using Matlab, how to generate a net of 3^10 points that are evenly located (or distributed) on the 8-dimensional unit sphere?
Thanks for any helpful answers!
- 173
2
votes
2
answers
5k
views
Best fit for multiple shapes inside an area
Is there a forumla to come up with the best fit for multiple shapes inside a rectangular area, so that none of the shapes are overlapping?
- 121
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 ...
