Questions tagged [packing-problem]

Questions on the packing of various (two- or three-dimensional) geometric objects.

Filter by
Sorted by
Tagged with
0
votes
0answers
15 views

How is those cases trivial in packing L's in Tans

In packing problem "L's in Tans" as presented on https://www2.stetson.edu/~efriedma/Lintan/. I don't understand how is some cases trivial and others are not. For example case $n=4$ isn't ...
0
votes
0answers
10 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://www2.stetson.edu/~efriedma/...
0
votes
1answer
30 views

uniform rectangle packing

I'm wondering if there is a formula or algorithm how many uniform rectangles of size $a\times b$ I can put in a square of size $c\times c$. Does anyone have a hint for literature?
0
votes
0answers
34 views

Upper bound on minimum distance between $n$ points on unit sphere [duplicate]

Suppose we have $n$ points $x_1,\ldots, x_n$ on the unit sphere in $\mathbb{R}^3$ (i.e. $\left\lVert x_i \right\rVert_2 = 1$). Is there a tight upper bound, as a function of $n$, on the minimum ...
0
votes
0answers
43 views

What seating configuration respects Covid-19 distancing but provides maximum packing?

I am a musician who plays in Celtic sessions. Typically 5 to 20 of us crowd into a pub or living room, but due to Covid-19 physical distancing recommendations, we now have to play outside in a big ...
0
votes
0answers
23 views

A compact set is negligible iff its packing number tends to $0$ as packing bound tends to $0$

A set $S$ is called epsilon separated if for any distinct $x$ and $y$ in $S$, $|x-y|>\epsilon$. Let be $K$ a compact set in $\mathbb{R}^n$, and let's define $P(K,\epsilon)$ as the maximum number of ...
1
vote
0answers
36 views

What are Voronoi cells for FCC and HCP Lattices lattices in space?

What are Vornoi cells for FCC and HCP Lattices ? (See plot below for FCC and HCP). Is my uderstanding correct that we should get one of the 5 "parallelohedra" ? If so, that seems to contradict ...
0
votes
1answer
41 views

Is it possible to fit more than 23 dots in a 7 by 8 rectangle?

For practical reasons I would like to know how many dots you can fit in an $7 \times 8$ box with no two dots closer than 2 metres from each other. The simplest arrangement has 4 dots along each row ...
2
votes
1answer
47 views

Find $\epsilon$ of a finite size $\epsilon$-net of a $d$-dimensional unit ball$

I have a set of $d$-dimensional vectors $V = \{+1, 0, -1\}^d $. Then $P(V)$ constitutes the power set of $V$. I now construct a set of unit vectors $V_{sum}$ from the power set $P(V)$ such that $$ V_{...
6
votes
1answer
94 views

What is the smallest diameter of a set of $n$ points in the plane which are all at least 2 meters apart from each other?

This question is similar to https://en.wikipedia.org/wiki/Circle_packing_in_a_circle except I am looking for the smallest diameter, i.e: I want the smallest maximum distance between the centers of the ...
0
votes
1answer
15 views

Knapsack problem on 2D or 3D space

Considering a series of rectangle items with known size $(a_1,b_1),(a_2,b_2)\cdots,(a_n,b_n)$, and a big rectangle box with size $(A,B)$ Question 1: How to fill the box with the items that minimize ...
2
votes
1answer
22 views

Given an abundant amount of money, how many times can you cover earth in coins?

To clearify the title, I am interested in the problem where we are trying to cover the surface of a sphere with cylinders. Let the sphere have radius R, the cylinders radius $r\ll R$ and cylinder ...
0
votes
0answers
26 views

Pack identical rectangles in a circle

I have identical rectangles of size (w, h). I would like to calculate the maximum number of such rectangles that I can pack (no overlap) in a circle of radius r. All the rectangles should also have ...
1
vote
1answer
42 views

Maximum number of $m\times n$ rectangles that fit in a $k \times k$ square

I'm sure this has been asked before but I have searched for ages and can't quite find what I'm looking for. Here's the problem: Essentially what is the maximum possible number of rectangles of a ...
2
votes
0answers
43 views

Is the circle packing game equivalent to the circle packing problem?

I came up with the following impartial combinatorial game. The game starts with an empty square with a given side length. The two players take turns, and in their turn, they place a circle of radius ...
0
votes
0answers
16 views

Trouble doing basic Apollonian Circle Packing

Good afternoon, I might be a bit a square because I can't seem to get the basics of Apollonian circle packing. I've used both the definition of curvature and Complex Descartes Theorem to draw the ...
3
votes
0answers
73 views

Validity of sphere-packing argument for converse channel coding theorem

The well-known capacity formula for additive white Gaussian noise (AWGN) channel is given by \begin{align} C=\frac{1}{2}\log_2(1+{\sf SNR}) \text{ [bits/channel use]} \end{align} where ${\sf SNR}=P/N$ ...
1
vote
0answers
12 views

Densest 3D packing of tori (toruses)

I have a 3D torus, say with radii $R$ (around the hole) and $r$ (thickness), where $R \gg r$. What is the densest packing, to fill a rectangular block with as many identical tori as possible? Tori ...
4
votes
0answers
42 views

Helical “packing” of deltahedra?

I'm looking for help with terminology: I'm a glass artist / PhD researcher aiming to use a modular, geometric approach to making. I've been looking to use repeated polyhedra (with regular polygonal ...
0
votes
1answer
24 views

Packing/tessellating 4 dimensional space fully by polytopes? Give examples.

What is a shortlist of first few simplest (say 5~10 simplest) possible shapes of polyhedra/polytopes (with a minimum number of edges shared) to pack the 4-dimensional flat space (say $\mathbb{R}^4$) ...
3
votes
4answers
73 views

Packing/tessellating 3 dimensional space fully by polytopes? Give examples.

What is a shortlist of first few simplest (say 5~10 simplest) possible shapes of polyhedra/polytopes (with a minimum number of edges shared) to pack the 3-dimensional flat space (say $\mathbb{R}^3$) ...
0
votes
0answers
27 views

Reduction of search space for NP-hard problem

I have a multi-objective optimisation problem. I proposed the use of the 2D bin packing, which is known to be NP-hard. But instead of having multiple bins at a time, only one bin is available, and the ...
0
votes
0answers
23 views

Least efficient method of packing unit squares into a circle?

I am wondering what the least number of unit squares that can pack a circle of diameter $k$ is. Consider a circle packed when you cannot fit another unit square inside it without it overlapping with ...
1
vote
0answers
75 views

Maximum number of non-overlapping spheres covering a sphere?

I would like to know if there is a formula, or at least some bounds, for the following problem. Consider a (three-dimensional) sphere of radius R. What is the maximum number of equal spheres, all of ...
0
votes
1answer
62 views

Circle packing problem [closed]

How did he calculate triangle packing in this site https://www.engineeringtoolbox.com/circles-within-rectangle-d_1905.html This site calculate number of circle in a square using 2 methods , normal ...
0
votes
0answers
16 views

On the Number of balls that can be placed inside a larger one.

Let $S_{R} = \{ (x, y, z) \in \mathbb{R}^{3} \mid \| (x, y, z) \| = R \} \subset \mathbb{R}^3 $, where $R >0$. Of course, $Vol (S_R) = \frac{4 \pi R^3}{3}$. I have been thinking about the ...
0
votes
0answers
25 views

Equitably allocating liquid across multiple uneven sized tanks

Is there a mathematical technique - ideally linear optimisation - for the following. I have a volume of liquid that I want to allocate equitably across multiple tanks. The volume added to each tank ...
3
votes
0answers
62 views

Packing spheres in a spherical space

Given a large sphere with radius $R$, and given a set of smaller spheres with radius $r$, how many smaller spheres can fit in the larger sphere. Ignoring the boundaries between spheres, the max ...
1
vote
0answers
26 views

2D topological packing problem with coalescing tiles

Given a complete set of 2-D connectable square tile "primitives" comprising: a "fully immersed" inner a 4-crossing a singleton two parallel outer edges, one horizontal one vertical four straight ...
1
vote
0answers
41 views

What is the maximum radius of $k$ spheres that fit inside a sphere of radius $r$?

I came across this problem the other day and couldn't figure out a way to solve it easily or any clear answer when searching in literature. Taking a sphere of radius $r$ in a 3 dimensional ...
8
votes
1answer
199 views

The largest equilateral triangle circumscribing a given triangle

Seven years ago, one of my many contributions to the March 2010 edition of Erich Friedman's Math Magic was a packing of eight circles of unit diameter and one equilateral triangle of unit side length ...
1
vote
1answer
99 views

Tiling a 4 X 11 board. [closed]

Prove that a 4 x 11 rectangle cannot be tiled by L-shaped tetrominoes.
5
votes
2answers
541 views

Can the Fibonacci lattice be extended to dimensions higher than 3?

I am interested in evenly distributing points on the surface of spheres in dimensions 3 and higher. This answer shows an excellent method called the Fibonacci lattice (also known as the Fibonacci ...
1
vote
0answers
70 views

Packing of consecutive cubes

Using the Ponting Square Packing, squares of size 1-49 can be packed in a 7x7 array so that the 25 interior squares are completely surrounded. Another way to look at the above squares is with the ...
1
vote
1answer
37 views

packing uniform cuboids into regular cube

I have a pile of uniform cuboids, of side a,b,c. I would like to make a regular cube. The sides are not in harmonic ratio ( cf. de Bruijn) but are in fact white sugar lumps. The minimum regular cube ...
11
votes
2answers
457 views

Packing of parallelograms with sides $1$ and $\sqrt{2}$ and angle $45^{\circ}$ in a rectangular container

If $ABCD$ is a parallelogram such that $\angle BAD=\frac{\pi}{4}$, $AB=\sqrt{2}$, $AD=1$ then we shall say that $ABCD$ is a good parallelogram. Parallelograms can be rotated by any angle. a) Prove ...
0
votes
2answers
51 views

Upper bound on width in packing problem

Suppose I have $n$ shelves and I'm supposed to store boxes in them starting from left to right. I have two types of boxes. For the first type of boxes $B_1$ I only know their total width, but I do not ...
2
votes
1answer
342 views

Is packing rectangles exactly into a larger rectangle NP-complete?

I want to pack a number of rectangles into a larger rectangle, however, unlike other questions that I could find, I would like to do so exactly, without allowing any wastage. I do not really care ...
0
votes
1answer
43 views

Circles of one integer diameter tightly packed around a circle of another integer diameter

Is it true that the only integer circle size you can tightly pack around another integer circle size is when the ratio between the sizes of the outer circles and the inner one is $1:1$? Do any other ...
0
votes
1answer
46 views

Packing 2x1x1 prisms into larger prisms

I'm currently having an issue where I need to pack 2x1x1 prisms into a larger prism of size 2x2x3. How many such ways is possible? What about for generic prisms of size 2x2xk? I've tried to figure ...
0
votes
1answer
31 views

Smallest circumcircle around four non-overlapping unit semicircles

What is the radius of the smallest circle into which will fit four unit half-disks? What arrangement of the half-disks achieves this? How is it proved optimal? The best arrangement I've found fits in ...
2
votes
0answers
78 views

How do I pack 2D objects into an arbitrary shape?

I've heard of packing problems in general, and I've seen a couple questions on this site that address specific cases (e.g. how to pack 45-45-90 triangles into an arbitrary shape), but after a search I ...
12
votes
2answers
148 views

Side length of the smallest square that can be dissected into $n$ squares with integer sides

Let $s_n$ be the shortest possible side length of a square constructed from exactly $n$ squares of positive integer side lengths. If no such square exists, let $s_n = 0$. The first few values are as ...
3
votes
1answer
98 views

T shaped tetris figures on a plane

I am just wondering how many (and by how many I mean countably or uncountably many) T shaped figures can we place on a XY plane. I assume that that T consists of 2 perpendicular lines and has 0 area. ...
2
votes
0answers
124 views

Equilateral triangle packing in the $l^1$ circle v.s. the $l^2$ circle

As established in a previous post Equilateral Triangles In The Taxicab Space there are exactly $8$ equilateral triangles (of edge length $1$) that can be packed in the $l^1(\mathbb{R}^2)$ unit circle, ...
0
votes
0answers
37 views

Irrational packing of Euclidean spaces (with no gaps).

This appears to be a new question on MSE. The only post on here after a search using the string irrational "packing" does not mention (explicitly) what I have in ...
3
votes
1answer
157 views

Equilateral Triangles In The Taxicab Space

It's fairly common to represent a unit circle in the Taxicab space ($1$-normed metric space) as a diamond in $\mathbb{R}^2$ with extreme points $(1,0), (0,1), (-1,0), (0,-1)$. What will an equilateral ...
2
votes
0answers
24 views

Given a set of points X, locate the ball of maximum radius whose interior contains none of the points in X

Suppose $d$ is a metric space. Let $X$ be a finite set of points and let $B_R(x_0)$ be some ball such that $X \subset B_R(x_0)$. Find the maximum radius $r$ such that there exists a ball $B_r(p)$ ...
4
votes
2answers
100 views

Optimal set of rectangle sizes to pack arbitrary rectangle?

I'm looking to build a set of wooden storage boxes of various standard sizes for storing small objects. I would like to choose a set of "optimal" box sizes (outside dimensions) for filling arbitrary ...
10
votes
4answers
388 views

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

I'm currently venturing through Paul Sally's Fundamentals of Mathematical Analysis. This is an unusual textbook in terms of the difficulty of exercises. I've already been stunned by the very first one:...

1
2 3 4 5
7