Questions tagged [packing-problem]

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

Filter by
Sorted by
Tagged with
4
votes
0answers
50 views

Is it impossible to fully pave this imaginary bathroom with some conditions?

Bob and Sarah decide to pave their bathroom floor with ceramic tiles. The bathroom measures $1.4$m by $3.7$m. A tile is a square slab with side length $30$cm. Tiles not closest to the walls of the ...
0
votes
1answer
33 views

In an $8\times 8$ square, what's the min number of dots to be placed so that there's always a pair with distance apart at most $\sqrt8$?

By the Pigeon Hole Principle (PHP), we know that when we are to place $17$ dots in an $8 \times 8$ square, then there will always be a pair with distance $< \sqrt8$. However, does PHP actually ...
0
votes
0answers
25 views

Circle packing in any shape

Is there a heuristic for packing a "maximum" amount of circles of radius at least 1 into any shape? Hex packing seems to be the most efficient, but sometimes there might be a strange shape ...
0
votes
0answers
9 views

Maximize surface area of Polycube given constraint

Given a Polycube constrained within $(a,b,c)$ cube, what's the largest surface area attainable? The entire thing need not to be connected. Assume $a,b,c$ are positive integers. Example when, $(a,b,c) =...
2
votes
1answer
68 views

Packing problem regarding a disc

Suppose that there is a packing of 1000 unit discs in the rectangle R. It means that these 1000 discs lie inside of R and any two of them do not share a common interior point (but they could touch ...
0
votes
0answers
34 views

Question on Erdos/Graham packing paper

I'm reading "On Packing Squares with Equal Squares" link . The paper deals with the problem of finding the most efficient packing of unit squares in a square of side length $\alpha$ where $\...
1
vote
1answer
50 views

How many spheres can fit inside a cylinder container?

So this is on the behalf of another friend for a school assignment. The assignment is: Find how many soccer balls fit inside a cylindrical building. Obviously, since a soccer ball is a sphere, the ...
0
votes
0answers
8 views

Same generator matrix implies same lattice?

Say there exists some lattice $L$ with a generator matrix $A$, As well, there exists some lattice $J$ with a generator matrix $B$, If $A=B$, is it necessarily the case that $L=J$? I know that the ...
1
vote
2answers
43 views

Linear Integer Programing: fill the package with products $A, B, C, D$

A linear integer programming problem ask to consider the next restriction: we want to fill as much as possible a package that has a capacity of $1m^3$ and we have to choose between a variety of ...
7
votes
1answer
56 views

Is the packing density of an ellipse the same as that of a circle?

It is well-known that the densest packing of circles in the plane is the close hexagonal packing, with a density of $\frac{\pi\sqrt{3}}6\approx0.9069$: By applying an affine transformation, we obtain ...
0
votes
0answers
24 views

Algorithm for Box Selection / Space Optimization

So, I have an optimization/space management problem. This same question is posted on two SE sites simultaneously, Stack Overflow and Mathematics, since I think it is fitting for both. Let's say I have ...
0
votes
0answers
40 views

Are “loose” circles typical in optimal circle packings?

There has been much work done on finding optimal packings of $k$ congruent circular discs in a larger circle; see here or here for a tabulation of many results. Scrolling through the results, one sees ...
0
votes
0answers
13 views

How to count the number of selected element in each slot within the packed ciphertext

Given an encrypted ciphertext (n slots, packed n elements into a single ciphertext), such as $ct=\{(2,0,1,2),(3,2,1,3),(3,4,0,4),(5,1,4,2)\}$. Formally, $n$ slots can be expressed as $m$ blocks, each ...
2
votes
1answer
22 views

How to create successive layers of Hexagonal Closed Packing?

How do I create a HCP using the bottom A layer? In other words, if I take the first layer and make a second layer, how much do I shift it vertically (z direction) and how much do I shift it backwards ...
1
vote
3answers
78 views

Minimum number of trips for a truck with weight limit of $200$ to transport boxes with weights 81, 73, 67, 49, 37, 34, 30, and 26

My 9-year-old son had the following math problem to solve: A truck can carry $200$kg or less. We have 8 different boxes with given weights: $81$kg, $73$kg, $67$kg, $49$kg, $37$kg, $34$kg, $30$kg, and ...
4
votes
1answer
59 views

Polyhedra which can be perfectly split into self-similar pieces

A cube can be perfectly split into smaller equally sized cubes. Similarly, a triangular prism can be perfectly split into smaller equally sized triangular prisms. Is there a name for or list of the ...
5
votes
1answer
76 views

How many generator blocks can I fit inside a $3\times3\times3$ cube?

In my Minecraft world I have a $3\times3\times3$ cube of space which I want to fill with $1\times1\times1$ generator and wire blocks. I can install a single outlet as part of the room's wall; it takes ...
7
votes
3answers
125 views

How good can a “near-miss” polyomino packing be?

Given a polyomino $P$ with $n$ cells, we can ask about its maximal packing density $\delta_P$ in the plane (perhaps the limsup if we are concerned about convergence issues, though I don't think this ...
6
votes
2answers
642 views

Unique question about packing problem

I added the related pages from part 3 of the book: combinatorial geometry by János Pach,Pankaj K.Agarwal (1995) (which is not available on net so I added them as pictures). A. Prove that one can ...
2
votes
2answers
28 views

How to calculate new box dimensions given a reduction in volume

I have a rectangular box with given dimensions $l, w, h$ with available volume $v = lwh$. If I can only pack up to 80% of $v$, how would I go about determining the new, smaller dimensions such that ...
0
votes
0answers
23 views

Summing squares within an irregular polygon

I am trying to know how many rectangles with a constant base and height (3mx1.8m) can fit inside an irregular polygon. To solve this, I'm taking the irregular polygon and putting small squares (0.6mx0....
3
votes
1answer
76 views

For a circle-Apollonian-packing problem, finding the smallest circle such that all natural numbers may be packed.

In section $1$ of the paper "The sequence of radii of the apollonian packing" of David W. Boyd, the author said that the question for the smallest circle into which disks of radius $1/n,n=1,...
4
votes
1answer
119 views

Rainbow covering by rectangles

There are $n$ coverings of the unit square, each of which contains $k$ axes-parallel rectangles of a unique color. Define a rainbow covering as a covering of the unit square that contains exactly one ...
1
vote
1answer
88 views

radius of nth circle inside a circle of given radius

A circle of radius 100 cm is given. The goal is to place 7 circles of unequal radius inside the initial circle, so that each 3 of circles don't overlap each other and all of them stay inside the ...
2
votes
0answers
66 views

Triangle inscribed and circumscribed gap-filling radii sequences distinct?

Staring with an equilateral triangle $\Delta$, inscribe a circle, then in the gaps, inscribe other circles, ad infinitum. Similarly, inside the circumscribed circle but outside $\Delta$, continue to ...
1
vote
0answers
32 views

What is (a lower bound of) the largest distance between two closest points in $[0,1]^d$?

Take a set of points $X = \{x_1,\ldots,x_n\} \subset [0,1]^d$ that includes the vertices of the unit hypercube $\{0,1\}^d$. Is there a known lower bound for $$ \max_{x\in X} \min_{y \in X} \|x-y\|_2\;,...
0
votes
3answers
101 views

What is the maximum number of T-shaped polyominos (shown below) that can be put into a 6x6 grid without any overlaps? The blocks can be rotated.

I just drew the figure and manually tried the question but I am wondering is there a way to do this problem via permutations and combinations. PS: I got answer as 7.
0
votes
0answers
23 views

An infinite packing in the plane with density $0$

Let $P$ be a packing in $\mathbb{R}^2$ consisting of infinitely many unit disks. Is it possible for $P$ to have density $0$? For clarification: A packing $P$ of $D \subset$ $\mathbb{R}^2$ is a set ...
0
votes
0answers
38 views

Lower bound on circle packings.

I am studying circle packings at the moment and I am trying to figure out, if there exists a lower bound on saturated circle packings with unit circles. In other words, I want to find the least ...
0
votes
0answers
17 views

tiling/packing maximum number of rectangules rectangles within polygons

I am looking for an algorithm to implement for packing rectangles within irregular polygon (with or without holes). So, given a polygon, and a rectange size, I would like to pack the maximum ...
0
votes
0answers
38 views

Volume of densely packed spheres

Please check the solution of calculating the volume of dence packed spheres. My approach was to calculate the amount of spheres in some volume. Coordinate x: Having the length lx and radius r, the ...
2
votes
2answers
64 views

Algorithm to get maximum number of n rectangles with given same width and height that fit into a rectangle with a given width and height

I am looking for an algorithm that can return the maximum number of rectangles in the same size with given width and height that fit in to a rectangle with given height and width. For an example let's ...
0
votes
2answers
72 views

Lower bound on number of disjoint spherical caps that can be packed on hypersphere

Let $S^n = \{x \in \mathbb{R^{n+1}: \ ||x||_2=1}\}$ be the L2 unit sphere in $\mathbb{R^{n+1}}$. I saw the following result (https://ocw.mit.edu/courses/brain-and-cognitive-sciences/9-520-statistical-...
12
votes
0answers
275 views

“Perfect” solutions to the kissing number problem besides in dimensions 1,2,8, and 24.

The kissing number problem asks how many n dimensional unit spheres can fit around a central one with no overlapping; a natural question is in what dimensions can this be done so that there is no ...
4
votes
2answers
67 views

Find minimum number of figures needed , so that no additional figure can be added?

I have a $6\times 12 $ rectangle, which I need to fill by the following figure: What is the minimum number of figures I need to use, so that no additional figure can be added? The figure can be ...
1
vote
0answers
50 views

Probably a fairly straightforward packing problem.

This is actually a real-world problem, although I've changed some details for privacy. I currently live in an old nursing home that used to house 50 people in individual rooms, but for various reasons,...
0
votes
0answers
30 views

Packing problem - cutting Penrose rhombus tiling from $M\times N$ rectangles (ceramic tiles)

Let's say I want to celebrate Sir Roger Penrose's Nobel Price with his unique tiling pattern in my bathroom (back holes are hard to come by). I guess the easiest shapes to cut from ceramic tiles are ...
0
votes
1answer
21 views

Lowest possible vertex density in a graph

What is the least amount of vertexes possible in a graph where the distance from any point on or around the graph to any vertex is at most $1$ unit of length? For example, a map covering $10$ by $10 \...
3
votes
1answer
122 views

Tiling a unit square with rectangles of area $\frac 1k \times \frac{1}{k+1}$ but not with those side lengths - any references (Web, book, etc.)?

A unit square can be tiled with rectangles in the following manner (please refer to the accompanying Figure). The first rectangle A is half the square. The next rectangle B is one-third of A; the next ...
1
vote
1answer
38 views

Maximum number of balls included in one ball

I guess this question has received an answer since a long time, but I was not able to find it (bad queries on Internet, I suppose): Take a ball $\mathcal{B}$ of radius $r$ in $\mathbb{R}^3$, for ...
3
votes
1answer
86 views

When packing disks into a square, is it best to be greedy?

The problem is to pack $n$ non-overlapping disks (not necessarily of the same size) of greatest total area into a unit square. The case $n=1$ is obvious: just place a disk of radius $\frac12$ ...
1
vote
2answers
63 views

What is the packing number of the unit cube?

The $\varepsilon$-packing number of the unit cube $[0,1]^d$ with respect to the infinity norm is the biggest number of $\varepsilon$-strictly-separated points, i.e., the biggest cardinality of a set ...
1
vote
1answer
64 views

Whats the maximum number of points inside a rectangle such that no two points have a distance less than one

Find the maximum number of points inside a 3 by 4 rectangle (the points CAN also lie on the perimeter) with the constraint that no two points have a distance less than one. someone suggested the ...
0
votes
1answer
25 views

Given fixed number of bins with equal capacity and variable number of items how many bins will I need?

I'm slightly embarrassed to ask this question as I feel that the answer might be exceedingly simple but I sat down to think about it and can't seem come up with a formula. I have a fixed number of ...
1
vote
1answer
71 views

Bin Packing Problem with fixed size of bins

I'm studying Bin Packing Problem for my thesis and I meet this definition of the decision verson of the problem in the book "Computers and Intractability" by Michael R. Garey and David S. ...
2
votes
0answers
46 views

optimal swarm plot packing

A swarm plot is a recently popular form of a scatter plot for one-dimensional data. Its basis is a set of $n$ real numbers, and each value is visualized by a marker, usually a circle of given radius. ...
1
vote
1answer
87 views

Maximum angle of separation between $n$ vectors in $m$ dimensions

My question is exactly as above. If there are $n$-vectors having the same origin in an $m$-dimensional Euclidean space then what is the maximum angle of separation that you can achieve. Example: In $...
6
votes
1answer
135 views

Impossible to pack Circles without gaps

It is intuitively apparent that circles cannot be packed without any gaps. I thought this is easy to prove, but it turns out not to me. I have $2$ versions for this question, which likely to have ...
0
votes
0answers
22 views

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

In packing problem "L's in Tans" as presented on https://erich-friedman.github.io/packing/Lintan/ . I don't understand how is some cases trivial and others are not. For example case $n=4$ ...
0
votes
0answers
19 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://erich-friedman.github.io/packing/...

1
2 3 4 5
8