Questions tagged [packing-problem]
Questions on the packing of various (two- or three-dimensional) geometric objects.
474
questions
0
votes
0
answers
14
views
Covering/packing number of a sphere instead of a ball
Let $\Theta$ be a subset of $\mathbb{R}^d$ with the Euclidean norm.
Let the covering number $N_2(\Theta, \epsilon)$ denote the smallest $n$ such that there exists a covering $\{\theta_1, \ldots, \...
- 87.3k
0
votes
0
answers
48
views
Max circle packing in a square
There are two types of circles, alpha circles and beta circles. Alpha circles have radius $r$, beta circles have radius of $1/r$. And, these two types of circles have to be fit into a square of length ...
3
votes
0
answers
77
views
Maximum tiling by Y Hexomino
"Y Hexomino" has a shape as shown in the picture.
What is the maximum number of Y Hexomino that can be placed on a $13\times 13$ chessboard, where each Hexomino does not overlap?
From the ...
- 183
0
votes
0
answers
25
views
Stacking bricks of various dimensions
In my line of work, I do a lot of stacking and packing cuboids of various proportions. Recently I was tasked with finding a stable arrangement of 5x6 units per layer using 2x3(x1) unit blocks, and ...
- 401
0
votes
0
answers
27
views
Limit density of sphere packing on a spherical surface
Analagous to circle packing in a circle, let's consider sphere packing on a spherical surface. The little spheres all have the same radius. I think there could be 3 possibilities of packing: a. every ...
- 149
0
votes
0
answers
25
views
Limit density of circle packing in a circle
The circle packing in a circle can be found in
https://en.wikipedia.org/wiki/Circle_packing_in_a_circle
http://hydra.nat.uni-magdeburg.de/packing/cci/cci.html
As the number of little circles (packing ...
- 149
3
votes
0
answers
56
views
Seeking a (simple) proof that the sphere packing density is always less than $1$ in $n \ge 2$ dimension.
For each natural number $n$, we may define the (optimal) sphere packing density in $\Bbb R^n$ to be the number
$$
D_n = \limsup_{r\to\infty} D_n(r),
$$
where
$$\begin{align}
D_n(r) = \sup \Big\{ \frac{...
- 14.4k
0
votes
1
answer
67
views
Fractional covering and packing problems.
I found the fractional covering number of the graph in the figure. And as a result, I came across the result of 5/2. Next I wanted to show its equality with fractional packing number. I found the n-...
- 19
18
votes
2
answers
426
views
You have $n$ rectangles of area $1$ (and variable height). Pack as many as possible in a semicircle of area $n$. How many leftovers will there be?
You have $n$ rectangles of area $1$ (and variable height). Pack as many of these rectangles as possible in a semicircle of area $n$. How many leftover rectangles will there be, in terms of $n$?
How to ...
- 12.5k
1
vote
0
answers
33
views
Do perfect squared rectangles with corners of sizes 10, 12 and 13 exist?
A squared rectangle is a rectangle dissected into squares.
squared rectangles are called perfect if the squares in the tiling are all of different sizes and are positive integers.
The smallest perfect ...
0
votes
1
answer
42
views
How many spaced squares fit in outer square
Say I have an outer square like this, which is 14m x 14m. Each inner square is separated by a space of 3m, and one square is 1m$^2$. I of course have the image up, but how would I mathematically ...
- 41
0
votes
0
answers
40
views
Find a sphere tangent to four other
I am working in an algorithm to order a bed of close-packed spheres. In the case where I have got four spheres, I understand that the fifth sphere position and radius is determined by the positions ...
1
vote
0
answers
64
views
What does the + sign mean at the end of a calculation result?
I discovered yesterday the Square packing in a square problem, and I ended up on this page that shows the proven answers for the first 89 values of $n$.
But at the end of some answers, we can see a ...
- 11
1
vote
1
answer
76
views
Using algebra to figure out how many boxes fit in an area without over estimating
I'm trying to figure out how many boxes fit in a specific area without over-estimating. The problem is the width of the space isn't a whole number multiple of the width of the boxes, the depth isn't ...
- 177
0
votes
2
answers
35
views
Sum of fractions in the form $\frac{1}{n}$ from $\frac{1}{2^n}$ to $\frac{1}{3*2^{(n-1)} - 1}$ less than $\frac{1}{2}$?
https://mathoverflow.net/a/278290/501460
I've been trying to figure out why this works, and why the tiles don't go past the middle, considering all the squares together have an infinite side length.
...
- 3
4
votes
1
answer
205
views
Total placement number of battleship game
The board is 4x4 and there are three types of battleships: 3x1, 2x1, 1x1. One for each type. How many total placements are possible? Notice, the ships cannot overlap and we must use all ships.
(there ...
- 151
1
vote
0
answers
36
views
Fomin et al., Mathematical Circles Chapter 4- Pigeon Hole Principle Problem 12. Max. no. of kings that can be placed so no two put each other in check
I found this problem in Mathematical Circles in the Pigeon Hole Principle chapter:
What is the largest number of kings which can be placed on a chessboard so that no two of them put each other in ...
- 2,429
0
votes
0
answers
15
views
Hyper-sphere packing inside the unit hyper-sphere vs on the surface.
Given a radius $r$ and a dimension $d$, what is the the factor between the number of $d$-dimensional hypher-spheres of that radius that can be packed into the internal volume of the $d$-dimensional ...
- 1
3
votes
1
answer
73
views
Does a (5,3,4)-code exist?
I am a bit confused on whether a binary (5,3,4)-code exists.
As far as I am aware, this code exists if and only if a binary (4,3,3)-code exists according to Theorem 2.7 in Raymond Hill's book "A ...
- 207
8
votes
0
answers
162
views
Marjorie Senechal (2011): "The question of packing tetrahedra is still unsolved" Is it still unsolved in 2023?
At about 15:49 in her 2011 talk Prof. Marjorie Senechal - "Quasicrystals Gifts to Mathematics":
But Hilbert understood that groups aren't everything and maybe not even the main thing. And ...
- 1,752
1
vote
1
answer
69
views
$1$-Lipschitz $f:[0,1]^k\to[0,1]^n$ With Maximally Dense Image
Is there anything known about which $1$-Lipschitz functions $$f:(X:=[0,1]^m)\to(Y:=[0,1]^n)$$ for $m$ < $n$ fill the codomain maximally dense, i.e. I want to minimize $\sup_{y\in Y}d(y, f(X))$ ...
- 3,462
0
votes
0
answers
43
views
Calculate a box closest to some limit that fits in a larger box
I'm not sure how to summarize this problem in the title and see a bunch of seemingly related Q&As but I didn't find one that fits this particular issue.
I have box with limits in 3 dimensions (...
- 101
5
votes
1
answer
273
views
The minimum rectangle area that can contain both triangle and circle.
I got this problem during my interview and I would love to find a good answer to this.
Problem: Given a circle radius equal to r and an equilateral triangle each ...
- 53
14
votes
1
answer
320
views
Frame challenge: Find the maximum $n$ such that circles of radius $1, \frac12, \frac13, ..., \frac1n$ can be held immobile by a convex frame.
Find the maximum $n$ such that circles of radius $1, \frac12, \frac13, ..., \frac1n$ can be held immobile by a convex frame, or show that there is no maximum.
Here is an example with $n=7$.
By "...
- 12.5k
0
votes
0
answers
48
views
Rectangles of certain Area fitting into larger rectangle of certain dimensions
I have an issue where I need to do the following:
Smaller rectangles (e.g., any size, but must have Area = 100 sq. ft.) must fit within another, larger rectangle (e.g., dimensions = 400 x 600 feet) ...
- 9
25
votes
2
answers
587
views
What is the minimum area of a rectangle containing all circles of radius $1/n$?
What is the minimum area of a rectangle containing all (non-overlapping) circles of radius $1/n$, $n\in\mathbb{N}$ ?
The total area of the circles is finite: $\sum\limits_{n=1}^\infty \frac{\pi}{n^2}=\...
- 12.5k
8
votes
4
answers
369
views
Four circles on a quarter disk: can the circles move?
Four unit circles are on a quarter disk. In the beginning, their centres are the vertices of a square, with two circles each touching a straight edge of the quarter disk, and the other two circles ...
- 12.5k
1
vote
1
answer
88
views
Circle packing: is every optimal arrangement unique?
For a given shape (e.g. square) and a given number (e.g. 15) of non-overlapping unit circles in the shape, there is an optimal arrangement of the circles that minimizes the area of the shape. (...
- 12.5k
3
votes
2
answers
208
views
Three circles in a triangle: can the circles move?
Three unit circles are in an isosceles right triangle. In the beginning, each circle is tangent to the other circles and one edge of the triangle; there is a vertical line of symmetry.
Can the ...
- 12.5k
0
votes
1
answer
49
views
Proof of relation between radii in hexagonal packing of 12 circles in a circle
I have 12 circles of radius r arranged in hexagonal pattern inside a container circle of radius R.
Picture of 12 equal circles packed inside a container circle in hexagonal pattern
This is not the ...
22
votes
4
answers
1k
views
Five circles in a rectangle: can the circles move?
Five unit circles are in a rectangle. In the beginning, their centres are the vertices of a regular pentagon, and each circle is tangent to two other circles and one edge of the rectangle.
Can the ...
- 12.5k
1
vote
2
answers
88
views
Purpose of perfect codes
Let $C$ be a $(n,M,d)_q$-code where $q$ is the cardinality of the code alphabet, $n$ is the codeword length and $d$ is the minimum Hamming distance of the code, i.e.,
$$
d=\min\{d(c,c'):c\neq c', c,c'\...
- 35
0
votes
1
answer
100
views
How many circles of radius R with a D distance between them, fit in rectangle of B x L
i have a rectangle of B x L meters and i want to know how many circles with R radius can fit if there is a space of D between them. All the values wil be integers always.
I tried this.
With this ...
1
vote
1
answer
55
views
Given 3 circles with different center coordinates and radius, what is the maximum radius of the circle that can fit inside the 3 circle in 3D?
In the context of determining pore volumes in adsorbing materials, I'm trying to find the pores that a gas molecule can go through. To do so, I need to solve a geometry/linear algebra problem. Here is ...
- 73
5
votes
1
answer
204
views
Given 4 spheres with different center coordinates and radius, what is the maximum radius of the sphere that can fit inside the 4 sphere?
In the context of determining pore volumes in adsorbing materials, I'm trying to find the pores that a gas molecule can go through. To do so, I have so solve a complex geometry/linear algebra problem. ...
- 73
5
votes
1
answer
129
views
Determine relative position of 3 large (equal) circles and 1 smaller circle within a minimum enclosing circle
I want to visualize the position of $3$ large equal circles with radius $r_1$ and $1$ smaller circle with radius $r_2$. The circles represent three wire conductor phases and one smaller neutral ...
- 53
4
votes
1
answer
96
views
Longest path/snake in 2D and 3D space
Recently I was reminded of an old blogpost I wrote about packing a snake-like path into 2D space (https://www.royvanrijn.com/blog/2019/01/longest-path/).
I never bothered to research this; try to find ...
- 249
1
vote
1
answer
82
views
Doubling constant (dimension) of $R^3$ under $L_1$ metric [closed]
What is the doubling constant of $\mathbb{R}^3$ under $L_1$ metric?
i.e. how many $L_1$ balls of radius $1/2$ are needed to cover an $L_1$ ball of radius $1$?
Note that an $L_1$ ball in $\mathbb{R}^3$ ...
7
votes
1
answer
238
views
Why does packing exactly 992 circles in a square behave exceptionally?
It is not so surprising that the problem of Circle packing in a square is a chaotic and often-unpredictable problem. However, after looking over the data on hydra.nat.uni-magdeburg.de, we find quite ...
- 4,448
4
votes
1
answer
238
views
Covering the surface of a sphere with circles with least overlap
By covered I mean every point is inside or on a circle. I can explain this best in flat space where, if I take a circle and pack it with smaller circles, then it seems I can increase the radius of the ...
- 63
0
votes
1
answer
121
views
2D packing problem, as a puzzle.
I have discovered a 2D packing problem that I cannot find the tools online to solve, so I have decided to present it to the Mathematics Stack Exchange as a fun puzzle.
In this problem there exist 4 ...
2
votes
1
answer
87
views
optimization: transport balls in a box so that the surface of the box is as small as possible
To transport $n$ balls with diameter $d>0$ a cuboid box should be constructed so that the surface of the box is as small as possible. Model this problem as an optimization problem. Is the ...
- 442
1
vote
2
answers
50
views
Bin packing with load fairness across the bins
The bin pack problem denotes the process of assigning a set of n items into a minimal number of bins of capacity c. It can be simply formulated as an ILP as per the below description:
My question is :...
- 111
0
votes
1
answer
43
views
In the allocation of objects in boxes, how to minimize the variance of total weights of the boxes?
There are N boxes (indexed as n1, n2, n3, etc.), and M objects of different positive weights each (weights m1, m2, m3, etc. The objects are ordered in a way so m1≥m2≥m3≥...).
The objective is ...
- 101
0
votes
2
answers
83
views
Algorithm for optimal partition of a multiset with bounded sum.
Consider the following problem:
Let $S$ be a multiset (you can think of it as an array) of positive
integers. Given a bound $W\geq \max(S)$, we want to find a partition
of $S$ into multisets $\{S_1,.....
0
votes
1
answer
45
views
Packing Points into Region with Variable Distances
This could be linked to the Packing Points into Region question. I have a rectangular grid with some positions occupied and need to place different types of points into the region with the distance ...
2
votes
1
answer
210
views
Place rectangles minimizing unused space
Given a set of rectangles $S := \{R_1, R_2, ..., R_n\}$, I want to place them on a canvas such that the bounding box contains as little unused space as possible. Rectangles must not overlap. Rotation ...
- 121
1
vote
1
answer
56
views
Maximum number of distinct elements in matrix of size $p \times p$, given for any row/column, there are $\le p-1$ distinct elements.
Prove that for any given prime $p \ge 5$, there doesn't exist any matrix of size $p\times p : [x_{i,j} | i,j\in \mathbb{Z}, 0\le i,j \le p-1]$, such that
$\forall i_0, \exists j_1, j_2 (x_{i_0,j_1} = ...
- 666
0
votes
0
answers
60
views
A Game of Placing Points in a Square
Suppose I have a unit square, and I mark some number of points in it with my pen wherever I like. Then I mark a final point, and I must place this final point at the center of the largest possible ...
- 580
2
votes
1
answer
78
views
On a covering of an $N\times N$ chessboard such that each black square is next to a covered square
Consider an $N\times N$ chessboard where $N$ is an even positive integer. Determine the smallest amount of pawns one must place on the board such that each black square is next to at least one pawn.
...
user992535