Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [packing-problem]

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

0
votes
1answer
32 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
36 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
15 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 ...
0
votes
0answers
24 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 "...
2
votes
0answers
60 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 ...
11
votes
2answers
96 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 ...
0
votes
0answers
9 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 ...
3
votes
1answer
61 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. ...
1
vote
0answers
43 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 ...
0
votes
0answers
33 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
103 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
22 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
48 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
298 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:...
0
votes
0answers
43 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 ...
6
votes
1answer
100 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 ...
0
votes
0answers
34 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 ...
18
votes
4answers
320 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 ...
3
votes
1answer
38 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 ...
2
votes
1answer
31 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 ...
0
votes
1answer
69 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 ...
0
votes
2answers
65 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?
0
votes
0answers
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 ...
1
vote
0answers
45 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)$, ...
1
vote
1answer
52 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 ...
0
votes
0answers
58 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. ...
6
votes
0answers
101 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 ...
2
votes
0answers
60 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 ...
4
votes
0answers
75 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$"...
1
vote
1answer
115 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 ...
7
votes
1answer
157 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 ...
0
votes
0answers
36 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!)
1
vote
1answer
45 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 ...
0
votes
0answers
43 views

Where can I find an example of using the ant colony optimisation method for the knapsack problem?

I could not find any examples of solving the knapsack problem using ant colony optimisation (have only found the description of a method). Does anyone have links to resources for this?
3
votes
1answer
395 views

Optimally packing $160 \times 80 \times 40$ boxes into a $1250 \times 230 \times 260$ space

What is the largest number of boxes of sizes $160 \times 80 \times 40$ that can be located in a space of $1250 \times 230 \times 260$ (long, wide, high)? In a very crude way, I managed to locate $3\...
1
vote
1answer
483 views

how to calculate the crosssection area of a bundle of tubes/cables

First of all, my mathematics skills don't allow me to understand regular formulas as I didn't get the whole mathetics thing to work for my brain until I discovered excel at the age of 20, and how to ...
4
votes
1answer
101 views

Fit a set of rectangular blocks given in a random order into a minimum volume box

Given a set of blocks whose length, width, and height respectively are $A:1 \times 3 \times 2$, $B: 2 \times 2 \times 1$, $C \text{ and } D: 2 \times 1 \times 1$, and $E,F,G\text{ and }H: 1 \times 1 \...
1
vote
3answers
110 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. ...
0
votes
1answer
88 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, ...
3
votes
0answers
107 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 ...
3
votes
0answers
57 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 ...
2
votes
0answers
55 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 ...
0
votes
1answer
216 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 ...
3
votes
0answers
111 views

Packing $n$-diamonds in a $n$-cube and a number theoretic conjecture?

Background Recently I was doing some recreational mathematics and stumbled across an interesting observation: What is the maximum number of diamonds (square rotated at $45^o$) can one fit into an $n ...
1
vote
1answer
211 views

What is the maximum number of non-overlapping circles that can be placed inside an ellipse?

Consider a standard ellipse of equation: $$\dfrac{x^2}{a^2}+\dfrac{y^2}{b^2}=1$$ and let the circle be given a radius $r$. Is there some algorithm useful to calculate it?
2
votes
1answer
778 views

Equilateral Triangle within a Rectangle

My friend wants me to answer her math challenge. She wants me to find how many equilateral triangles can be acquired from a rectangular sheet. See image below for the dimensions: I calculated the ...
5
votes
1answer
298 views

Can the squares with side $1/n$ be packed into a $1 \times \zeta(2)$ rectangle?

As is well-known the total area of the squares with sides $1, 1/2, 1/3, 1/4, \ldots$ is $\pi^2/6$. But can a $1 \times \pi^2/6$ rectangle be tiled with those squares? I have packed the first $10^{10}$ ...
1
vote
1answer
51 views

Circle packing 2nd column distance from left side of square

Do I have it right that the top circle in the 2nd-column to the right of the below packed square is $r(\sqrt{3}+1)$ units to the right of the left edge of the square. And by "is" I mean where the top ...
0
votes
2answers
60 views

Number of pixels covered by an oval.

I have a raster image with an oval inscribed in a rectangle with a given width and height (in pixels). I need an efficient (ultra-high resolution picture) algorithm to compute the exact number of ...
1
vote
1answer
154 views

How do I calculate the distance between the center points of ellipses in a face centered cubic lattice?

I am currently writing a mathematical essay concerning the close packing of various 3D shapes. One example I am investigating is the shape of an oblate spheroid (ellipsoid) with a minor axis of 5 mm ...