# Questions tagged [packing-problem]

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

297 questions
13 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 ...
19 views

### Algorithm to arrange different-sized circles in a square area?

Suppose I have a large square and a set of $n$ circles, each with a different radius $r$, such that there exists some way to fit all the circles into the square. Is there an algorithm to find the "...
34 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 ...
91 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 ...
7 views

### Two-level bin packing in semi-unrestrained space

I have a bin packing problem. Manually-packed bins image We start with anywhere from 50 to 2000 individual squares of identical size. These squares are packed into rectangular groups of different ...
58 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. ...
42 views

### Is this problem existing or interesting? [closed]

Recently, I came up with a mathematics-based puzzle which in a way could be linked to the packing problem, but differs from it significantly at least in my opinion. Before further ado, the question ...
87 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, ...
31 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 ...
98 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 ...
21 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)$ ...
45 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 ...
286 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:...
37 views

### Reference request: Good introduction to Sphere Packing

I was hoping someone could recommend a good introduction to the theory of sphere packing. I know that this is a problem that has received some attention lately, due to the solution of this problem in ...
96 views

### Can 27 points be packed into a 3x3x3 cube and all be more than $\sqrt{3}$ from one another?

This problem comes from a math test which I've already completed. I'll give the problem and my attempt at a solution. Part A: Given a $3\times3\times3$ cube $C$ containing 28 points. Prove that some ...
30 views

### Is there an algorithm for breaking symmetries in polycube puzzles?

Does there exist a general algorithm for dividing a polyomino/polycube packing problem into a set of subproblems which if solved will produce in aggregate all solutions to the original problem, but ...
308 views

### How many colors are necessary for a rectangle to never cover a color more than once?

If we have an infinite grid, and we color each cell, how many colors do we need so that a $m \times n$ rectangle always covers at most 1 of each color no matter how it is placed? (Rotation of the ...
30 views

### A conjecture about minimal spanning trees among points in the unit square

For $n\in\Bbb N$, consider $n$ points $x_1,\ldots, x_n$ in the unit square $Q=[0,1]^2$. Let $f(x_1,\ldots, x_n)$ denote the minimal total edge length of a tree with $x_1,\ldots, x_n$ as vertices. Let ...
30 views

### Packing densities in grid world

Suppose there is a 25x50 grid world with 1250 grid cells. Suppose some of them are colored black (full) and some are white (empty). We are interested in quantifying the packing of this grid world. If ...
67 views

### Word problem about volume

Hello I have been trying to solve this word problem but am not sure how to start, I would appreciate some help. What is the maximum number of bottles, each of diameter $9$cm, that can be packed into ...
62 views

### Volume of air in the box (packing problem)

Suppose I have a box with dimensions $L \times W \times H$. What is the volume of air in the box, if I pack balls with radii $r$? With increase of radius, does volume of air decrease?
18 views

### Find all packings of widgets by a set of requirements: is this a linear programming or combinatorial optimization, or bin packing problem??

Can not determine if this is a linear programming problem, or a combinatorial optimization problem, or even a packing problem? Goal is to allocate widgets from the inventory to fulfill all shipping ...
41 views

### How to distribute N approximately equispaced points with a given probability density?

Let $x_i$ be points in $R^D$ space, $i = 0\ ..\ N-1$, where $N$ is fixed. The problem is to distribute the $N$ points in the space so that their density is equal to given probability density $p(x)$, ...
49 views

### Up to 6 points spaced $r$ apart can fit on a rectangle of dimensions $(r,2r)$

Consider a rectangle of dimensions $(r,2r)$. Is it true that one can place only up to 6 points spaced at least $r$ apart from one another in or on the rectangle? One can place the 6 points on the ...
53 views

### Radius of sphere tangent to eight spheres in a close packing

Assuming I have a cube of size a which already filled with 8 spheres with radius of a/4. I would like to find the radius of the sphere tangent to all this 8 and fill the hole at the center of cube. ...
98 views

### Gardening problem - mass planting in a circular area

First of all I am not a mathematician, forgive me if this is a stupid question. A circular area is given. How to place n plants within the area so that the minimal distance between any of two plants ...
52 views

### Optimal packing of a tile without rotation or reflection

Let's say we have a shape. We will call this shape $A$ and we will say that $A$ is some finite subset of the regular square tiling. Similar to a polyomino, except we do not require that $A$ has a ...
72 views

### Does infinite mikado exist?

Let's define a mikado configuration $m$ as a countable collection $\{T_j\}_{j \in \mathbb{N}}$ of disjoint subsets of Euclidean 3-space $(\mathbb{R}^3,\cdot)$. Each $T_j$ is a "tube of radius $R>0$"...
103 views

### Looking for help developing an algorithm to solve a 2D rectangle packing/bin problem.

I need to develop an algorith to determine the optimum packing arrangement of dimensionally identical rectangles in a large rectangle of fixed size. 90 degree rotations are permitted. I've researched ...
145 views

### Packing problem - how to fit things nicely with just the aspect ratio of the objects

Suppose you have a rectangle that is w units wide and h units tall (bounding rectangle). You also have an even ...
33 views

### Hyper-sphere packing in dimension 9

What is the best known lattice for sphere packing in dimension 9? The 'best' lattice is still unknown in dimension $d>8$ (except for the famous d=24!)
41 views

### Nesting Problem: Randomly-Generated Rectangles In Series Within Larger Rectangle

How efficiently can randomly-generated rectangles be nested within a larger rectangle of defined width (say, 30”) and fairly long length, where each inner rectangle must be placed/nested permanently ...
40 views

### Coin packing problem info?

I drop coins of various denominations into my piggy bank - pennies, dimes, nickels, etc. They all obviously have different volumes & weights. I drop them in according to a known distribution - ...
35 views

### Where i can find example of ant colony method for knapsack problem?

I could not find example of solving the problem of a backpack by the method of an ant colony. Has found only the description of a method. If you know where to find please help.
357 views

107 views

### Packing Points into Region

In a $64\times 200$ region, the distance between any two points must be at least $25$. What is the maximum number of points that can be placed inside the region? The most I could fit was 30. ...
80 views

### Size dependence of density of random close packing (for spheres)

I was reading about random close packing of spheres on Wikipedia and Wolfram Mathworld, and if I did not interpret both incorrectly, the conclusion is that if I pack a volume V randomly with spheres, ...
99 views

### Tetris: What is the Polyomino (max 3x3) with the least probability of being useful to the player?

I am currently programming a Tetris game and I want to add a custom Polyomino to the game with a maximum size of 3x3. I want this Polyomino to be the most disruptive figure, which means it to be not ...
56 views

### Orthogonally packing consecutive integer cubes 1x1x1 -nxnxn inside the smallest integer cube.

For small n, the problem of orthogonally packing consecutively sized integer cubes 1x1x1 - nxnxn inside the smallest integer cube CxCxC is trivial. By inspection, the sizes of two largest cubes n and ...
52 views

### Does finding the line of tightest packing in a packing problem help?

Background I've been recently been thinking about the packing problem. I noticed something odd. In the case of tight packing (no jiggling of a particular part of the packages if the container is ...
207 views

### Pack three largest sphere in a cube with given length.

I'd like to ask about sphere packing problem. The question is: Pack three largest and identical sphere in a cube with a given length 1. Find the diameter of the sphere. And can you kindly also draw ...
111 views