Questions tagged [packing-problem]

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

Filter by
Sorted by
Tagged with
1 vote
0 answers
13 views

What will be the upper bound of covering number of $r B_{n}^2$

I am very curious to know The covering numbers of the r-radius Euclidean ball $B_{n}^2$ for any $r$ > 0: so $r B_{n}^2$ is a Euclidean ball with radius $r$ Have read this but unable to find. Can ...
user avatar
  • 280
1 vote
0 answers
29 views

Finding the smallest box that would fit different sets or stacks of other boxes

I am trying to find an efficient way of solving this. I have 3 sets of boxes. Each set of boxes goes together. I want to find a one size bigger Box that can hold each of these sets. By this I mean one ...
user avatar
0 votes
0 answers
20 views

Approximation for maximum space 2D irregular bin packing

So usually bin packing algorithms compute the tightest packed solution. I want to calculate the opposite, in my case the solution with the most space between the packed objects is needed. I tried ...
user avatar
2 votes
0 answers
84 views

Which shape is the worst to pack in $\mathbb{R}^n$?

Yesterday I bought a box of chocolates and remarked with a friend how they had just put enough in to get above a certain transparent window to the inside but everything else was empty space. I added ...
user avatar
  • 2,450
2 votes
0 answers
52 views

Articles from the Journal of Recreational Mathematics from the 1970s

When reading some articles about packing puzzles I regularly stumble accros references from the "Journal of Recreational Mathematics" from the 1970s. I did not found any way of accessing ...
user avatar
  • 639
0 votes
0 answers
30 views

Where do the "classical lattices" come from?

I am trying to understand sphere packing problems, and it seems well-known that lattices can be only of certain kinds: the classical types (e.g. $A_n, B_n$, etc.) or the exceptional types (e.g. $E_8$)....
user avatar
  • 491
0 votes
1 answer
22 views

How to fill a $d$-dimensional rectangle of shape $n_1 \times n_2 \times \dots \times n_d$ with $k$ points homogeneously?

Given a $d$-dimensional rectangle ("hyper-rectangle"?) $$A = [0,n_1]\times[0,n_2]\times\dots\times[0,n_d]$$ with $n_1,\dots,n_d\in\mathbb{R}^+$ How to fill it with $k$ points homogeneously? ...
user avatar
  • 1,801
5 votes
2 answers
336 views

Number of plates that can be placed on the table so that they neither overlap each other nor the edge of the table?

Table in my room is round in shape and its radius is 15 times the radius of our plates, which are also round in shape. Find the number of plates that can be placed on the table so that they neither ...
user avatar
  • 358
0 votes
0 answers
44 views

How to prove that a square packaging problem has an optimal solution?

In a mathematics book "Which way did the bicycle go" were given a problem: What is the smallest square into which you are able to fit 11 unit squares without overlapping. There were no ...
user avatar
2 votes
1 answer
84 views

Understanding the Honeybee Conjecture vs. Sphere Packing Conjecture

I am trying to understand the differences between the Honeybee Conjecture and the Sphere Packing Conjecture (also called the Kepler Conjecture). As a quick overview: "The honeycomb conjecture ...
user avatar
1 vote
3 answers
75 views

How much wire will fit on an industrial reel?

I am trying to figure out how much cable would fit on an industrial reel. I have found a few calculators but nothing that will help me calculate this myself. If you have a reel with dimensions of 3m ...
user avatar
  • 13
1 vote
0 answers
11 views

Epsilon Packing Bounds for a unit hypercube

Let S denote the hypercube $[0, 1]^d$ . What are the best upper and lower bounds you can prove for $n_{pack}(S,ε)$ as a function of ε and d? Justify your bounds with proofs. You may assume that $ ε &...
user avatar
0 votes
0 answers
19 views

Optimal sphere packing maximizing the number of contacts

I read about the optimal sphere packing and packing spheres into a sphere. But I was wondering if there was a result for packing spheres while maximizing the number of contacts between spheres ? This ...
user avatar
  • 323
1 vote
1 answer
47 views

Trying to Resolve One Recursion with Two Solutions

Background: I recently answered a question about the sequence of minimum Ford circles on each successive iteration here. I then asked myself the related question about the maximum circles on each ...
user avatar
  • 6,213
1 vote
1 answer
114 views

Proving that $81$ $K_4^3$'s cannot be packed in a doubled $K_{11}^3$

The sequence $T_{2,m}$ in Guy's 1967 paper A problem of Zarankiewicz describes the maximum size of a collection of $4$-subsets of $\{1,\dots,m\}$ such that every $3$-subset is in at most two of the $4$...
user avatar
  • 89.6k
2 votes
2 answers
63 views

What kind of non-optimisation packing problem is this?

You start with a big 2D shape (irregular polygon), and a set of smaller shapes. The goal is to figure out if the smaller shapes can fit within the big shape, without any overlaps. Rotations are ...
user avatar
0 votes
1 answer
60 views

How many balls can fit in a house shaped box?

Consider the following house shaped box with the indicated measures: I need to get the best possible approximation of how many balls of 3 inches of diameter can fit in this box without exceeding the ...
user avatar
  • 2,441
0 votes
0 answers
41 views

Finding the largest polyominoes that can fit in a rectangular space

I am making a program that generates $3$ random polyominoes of size $x \le n$ (referring to the number of squares in the shape). Each polyomino fits within a space: $k \times k$ ($k=6$ in my case). I ...
user avatar
0 votes
0 answers
22 views

How much empty sphere is left over in the 3rd dimension?

I know the kissing number of a sphere in 3d space is 12, but I've also heard mention that there's a significant ammount of space left over, using a sphere of a whole fractional radius of the unit ...
user avatar
0 votes
0 answers
14 views

What algorithm can be used for packing identical cylinders into a rectangular prism in an optimal way in MATLAB?

I am trying to fit a maximum number of fixed-size cylinders into a fixed volume and plot them in 3D (e. g. image). The constraints are the fixed volume, dimensions of the cylinders, the gaps between ...
user avatar
3 votes
0 answers
125 views

Can you convert a packing with overlap to a packing without overlap?

There is a finite set $X$ of positive integers, and an integer $M$. A subset of $X$ is called packable if its sum is at most $M$. Suppose there are $2 n$ packable subsets of $X$, such that each ...
user avatar
0 votes
0 answers
31 views

Optimization problem with norm \geq constraints

I have the following optimization problem: $$\begin{array}{cc}\min&\sum_{i=1}^m||x_i-x_i'||_2\\\text{s.t.}&||x_i'-x_j'||_{\infty}\geq\lambda\end{array}$$ where $\lambda\geq0$ and $x_1,\ldots,...
user avatar
  • 203
0 votes
0 answers
51 views

algorithm for fitting different sized circles into a square

I have the following question. I want to stack differently sized circles into a square/rectangle in a pyramid pattern and write code that can calculate the amount of circles in it. Kind of like this. ...
user avatar
  • 123
1 vote
0 answers
34 views

Find $m$ (approx) maximally distant unit vectors in a unit $n$-sphere, where $m > n$

I want to find $m$ unit vectors on the surface of a $n$-sphere, where $m > n$ and the cosine angle amongst the $m$ vectors is maximal. There are a few posts on this particular problem (ref 1, ref 2,...
user avatar
  • 11
1 vote
0 answers
28 views

If two lattices have the same kissing number and center density, then are they similar?

Two lattices $\Lambda$ and $\Omega$ (the $\mathbb{Z}$-span of a linearly independent set $B\subset \mathbb{R}^n$) are said to be similar if there exist a real orthogonal $n \times n$ matrix $A$ and a ...
user avatar
0 votes
0 answers
37 views

2D packing problem - how to optimise/maximise area of a a set of irregular convex polygons within a polygon?

I'm interested in a particular case of this problem: fitting odd-shaped polygons/shapes within the bounds of a rectangle. Say you have 10 sticker designs and you want to fit them all on a sheet of A4 ...
user avatar
2 votes
0 answers
106 views

What is this branch of mathematics?

What is the branch and topic of mathematics concerned with volume optimization of objects that can be morphed/manipulated? I.e. finding the most efficient way to position 3D objects, where each object ...
user avatar
0 votes
0 answers
33 views

If you fill space with spheres and inflate them

Say that you were to fill space with spheres and inflate them what shape would the bounds make? We can assume the spheres are packed optimally, just like you would stack cannon balls, what kind of ...
user avatar
  • 99
1 vote
1 answer
62 views

Circle Packing - Average distance between a random point in a circle and the second, third, fourth, ... closest circle centre

I am currently working on the following problem (see also the example drawing): Suppose I have, for example, a hexagonal circle packing or a square arrangement. And we randomly place a point in a ...
user avatar
0 votes
0 answers
59 views

How to calculate the number of smaller rectangles that fit into a larger rectangle with minimum wastage.

I have a larger rectangle of 2438mm width x 1219mm height. I have smaller rectangles that I need to cut out from the larger rectangle. The ideal dimensions of the smaller rectangles are 200mm width x ...
user avatar
  • 101
2 votes
0 answers
63 views

Packing spheres in a sphere

For dimension $d$, let $N(r,d)$ = number of spheres of radius $r$ which can be packed in a sphere of radius 1. For dimension 1, $N(r,1) = \lfloor 1/r \rfloor$. From the articles below, I infer that $N$...
user avatar
  • 121
1 vote
0 answers
54 views

Packing maximum number of identical rectangles in a polygon

Given a 2D polygon, convex or nonconvex, maybe some holes (also small polygons) inside. How can we pack an (approximately) maximum number of identical rectangles in the polygon (the rectangle can not ...
user avatar
0 votes
0 answers
26 views

How can I solve the circle packing problem for 2 unitary radius circles using KKT?

I am trying to solve the packing circle problem for two circles with unitary radius using Karush Kuhn Tucker KKT conditions. But I am stuck with the following equations: Is it possible to solve the ...
user avatar
3 votes
0 answers
48 views

Why can't Pascal's Simplex with n terms be used to describe close-packing of equal n-spheres?

Pascal's simplex is a generalization of Pascal's triangle into n dimensions, just as multinomial theorem is a generalization of binomial theorem. In Pascal's triangle, binomial coefficients are ...
user avatar
  • 141
0 votes
0 answers
59 views

Are there semidefinite programming bounds for the number of kissing spheres in the upper hemispace with respect to the central sphere?

For dimensions n=5-7 there are good known lower bounds for the number of n-dimensional spheres that that can touch (kiss) the central sphere, but the maximum number of spheres that can do so is not ...
user avatar
  • 1
2 votes
1 answer
42 views

Optimal distribution of the playing cards on print templates

I have a mathematical Problem: I plan to have about 1200 cards printed for the open source game INCANTATA from ZeroNet. In doing so, I now come across the problem of distributing the cards on the ...
user avatar
  • 123
1 vote
0 answers
86 views

How many rectangles of different sizes can fit in a large rectangle, until you need to exchange the large rectangle for a bigger rectangle

I'm trying to figure out how to plan something without actually going out and buying the stuff. the title is pretty much the problem, but let me give an example let's say you have 2 rectangles of ...
user avatar
  • 11
0 votes
1 answer
34 views

Algorithms to find the allocation solution of placing items to bins that maximizes the number of total full bins

I have a problem that could be a variant of "bin packing problem". Input: Given $N$ identical items: $i_1, i_2, ...,i_N$ with the same weight (or volume). Given $M$ bins: $b_1, b_2, ..., ...
user avatar
1 vote
1 answer
90 views

How many different ways can you place a set of squares, each with integer side length, on a 2D grid of size N x N without overlapping?

The question can be understood as follows: You are given a set of $n$ different sized squares $S = \{ \left(K_1, L_1 \right), \left(K_2, L_2\right), ..., \left(K_n, L_n \right) \} $ where $K_i$ is the ...
user avatar
0 votes
0 answers
77 views

How many squares can fit in a circle without going outside the perimeter? [duplicate]

How many squares of side length $x$ can fit in a circle of diameter $n\cdot x$, where $n$ is any positive number, such that none of the squares overlap the perimeter of the circle and all of the ...
user avatar
0 votes
0 answers
44 views

What is a sphere packing?

We are currently dealing with (n,m,d)-codes (sphere covering bound, sphere packing bound etc.) and one question to solve is: We are now looking for a sphere packing of $\{0,1\}^6$ with radius $r$. ...
user avatar
  • 97
0 votes
0 answers
19 views

Can anybody prove the most compact configuration of N circles with unobstructed line-of-sight to the origin?

The problem is how to distribute N circles of radius r in the Real plane such that they each have a clear line-of-sight from their centers to the origin (i.e. not blocked by any other circles) in the ...
user avatar
-1 votes
1 answer
54 views

Obtaining a circle packing from a set of circle centers? [closed]

I want to grow circles centered at a set of $n$ points simultaneously and uniformly until a circle packing is created. Is there a way I can solve for the radii of the circles in the packing ...
user avatar
0 votes
1 answer
44 views

How can I quickly tell if a valid solution exists to pack smaller rectangles into a bigger rectangle without overlapping?

Can you always pack smaller rectangles into a single unique bigger rectangle (known in advance) without overlapping if Every smaller piece fits inside the bigger rectangle individually. The total ...
user avatar
2 votes
1 answer
73 views

Does sticking LEGO bricks together make them easier or harder to pack away into a box of fixed volume?

My son uses a lot of LEGOs that we have to clean up every night before he goes to bed. The box we use for them is a little on the small side, so we often find that the LEGOs are stacked too high for ...
user avatar
  • 63
0 votes
0 answers
65 views

Help with understanding if my way to solve the riddle works or not

So the riddle i was asked is: you have a circle, with a radius of 9, prove that you cant pack 101 points inside of it, without having at least a pair of dots with a distance less than 2 between them. ...
user avatar
3 votes
2 answers
87 views

Why doesn't an inscribed cube perfectly sample the surface of a sphere?

I was curious about ways to sample perfectly dispersed points on the surface of the sphere. This question had some interesting info: Is the Fibonacci lattice the very best way to evenly distribute N ...
user avatar
  • 43
18 votes
1 answer
307 views

How densely can the :...: polyomino fill the plane?

This is a follow-up to the question How good can a "near-miss" polyomino packing be?. Let $P$ be the heptomino shown below: I am interested in the packing density of $P$ on the square grid. ...
user avatar
3 votes
1 answer
349 views

Most efficient way to pack circles with different radii in a rectangle of given size

Given a rectangle of size $x$, $y$, I would like to fit the maximum circles in it. The second rule is that my circles come in 3 different radii $r_1$, $r_2$, $r_3$, and I need the maximum number of ...
user avatar
  • 131
0 votes
0 answers
52 views

How many possible fruit could fit in a box?

I'm bad at math and English so please forgive me. I have infinite fruits like apple, orange, and mango and I want to fit fruits in a box that has a volume of 100 units. If an apple has a volume ...
user avatar

1
2 3 4 5
9