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

learn more… | top users | synonyms

0
votes
0answers
27 views

Dense packing of circles in unit circle, matlab code

I'm having real difficulties with a packing problem: Given M circles with equal radius r, determine the maximum radius such that all the circles can be fitted into the unit circle, without overlap. ...
3
votes
0answers
30 views

Largest and smallest shape enclosed within circles

There is a convex shape $C$. It is known that the largest disc contained in $C$ has radius $r$ and the smallest disc containing $C$ has radius $R$. What are the smallest-area and largest-area shapes ...
0
votes
0answers
29 views

max number of circles in a circle using symmetrical packing

How many circles of radius 1 can fit into a larger circle of radius 40 using symmetrical (square) packing? Is there a general formula for a larger circle of radius r? For an example of such a ...
1
vote
1answer
77 views

Packing problem cube and cuboids

Is it possible to fill a box with dimensions $10\times10\times10$ using bricks of dimensions $1\times1\times4$? If yes, how? I think De Bruijn's theorem on harmonic bricks could be helpful, but I ...
1
vote
0answers
45 views

Proof: At most 3 circles of radius 1/2 fit into the interior of a halfcircle of radius 1

It is a well known fact that at most 7 interior disjoint circles of radius 1/2 can be centered in a circle of radius 1; note that they don't need to be fully contained in the radius 1 circle. I am ...
0
votes
0answers
59 views

Algorithm to optimize rectangles filling by rectangles

I have a set of rectangles, all of the same size (W,H) (in fact paper sheets). I have another set of n rectangles of different sizes (Wi,Hi), i = 1..n such that Wi <= W and Hi <= H (in fact ...
1
vote
0answers
19 views

Reference for packing-covering of the sphere.

I suspect the following to be true and well known. I am looking for a reference. About the notations: $d$ is the dimension, $S^{d-1}$ is the unit euclidean sphere in $\mathbb{R}^d$, $d(x,y)$ is the ...
9
votes
1answer
110 views

Can 23 of this polycube fit in a 5x5x5 box?

Consider the following pentacube (front and back view shown.) I have used Burr Tools to determine that 24 of these will NOT fit in a 5x5x5 box. According to my notes when working on this problem a ...
2
votes
0answers
82 views

How to load warehouse pallets efficiently?

Assume that we would wan't to develop a warehouse management system, which picks up plastick boxes and stacks them on a pallet. A pallet has a maximum of 5 vertical box stacks and the maximum height ...
0
votes
0answers
26 views

Calculating the package sizes

How can I calculate the minimum size of a package (paper box) that the product certainly fits in when the employees are warping them? I should be able tell how big boxes should be used for each ...
0
votes
1answer
44 views

Calculate remaining space of a box/cube

Im developing an eCommerce system where items are 'logically' placed into boxes. Rather than the shipping system calculating the shipping of each item individually. The shipping will be calculated by ...
12
votes
1answer
332 views

Packing an infinite sequence of disks

Let $a > 1$ and $Q(a)$ denote the supremum of values of $q$ such that a countably infinite collection of disks, whose areas form an infinitely decreasing geometric progression with the start value ...
2
votes
0answers
56 views

Packing circles in circle vs semicircle vs quarter of circle

Consider $N$ disjoint circles with radius $1$ packed into a larger circle $C$. Let $R$ be the smallest possible radius of $C$, allowing the best packing density. Now take the $N$ unitary circles ...
2
votes
1answer
144 views

Packing circles into circle of diameter 7

How many unit circles can you fit inside a circle of diameter 7 such that no circle overlaps any other circle? Please explain the concept or any tricky process regarding this problem.
8
votes
2answers
237 views

Visual illustrations of circle packing theorem?

Circle packing theorem states: For every connected simple planar graph G there is a circle packing in the plane whose intersection graph is (isomorphic to) G. Paper Collins, Stephenson: A circle ...
4
votes
1answer
126 views

10 points inside a square - minimum distance between any of them

A square of side 1 is given, and 10 points are inside the square. If we divide the square into 9 smaller squares, and apply Dirichlet principle, we can prove that there are 2 of these 10 points whose ...
0
votes
0answers
132 views

Periodicity of Ideal Packings on Arbitrary Boundaries

This is a question that's been nagging me for some time that I find particularly interesting, but have no idea how to go about solving it. Consider some arbitrary solid $S$, such that $\partial S$ is ...
0
votes
0answers
51 views

Sphere packing in high dimensions and boundary conditions

The Minkowski lower bound for packing hyperspheres of unit radii in $\mathbb{R}^n$ states that the density of hyperspheres satisfies, for all $n\geq 2$ \begin{equation} \Delta_n \geq ...
0
votes
2answers
60 views

Unusual 3D Packing Problem

I made up this interesting problem playing with wire sculptures: If I have a $10 \times 10 \times 10$ clear box and inside I can put wireframe unit cubes, what's the maximum number of unit edges (or ...
32
votes
2answers
830 views

Triangles packed into a unit circle

2014 triangles have non-overlapping interiors contained in a unit circle.What is the largest possible value of the sum of their areas? What are some ideas that might help me start this? Note that ...
0
votes
1answer
241 views

Maximizing minimum distance between points placed in a polygon

I would like to maximize the minimum spacing between a fixed number of points ($x_i \in \mathbb{R}^2$) placed inside a polygon in the plane. The minimum spacing includes distance to the polygon. ...
1
vote
0answers
64 views

Fitting a rectangle within another rectangle

What are the restrictions such that we can fix a rectangle of dimension $a\times b$ into another rectangle of size $c \times d$? What about if we try to fit it inside a square of side $c$?
2
votes
1answer
133 views

Packing spheres on the boundary of a larger sphere

Consider the following problem, which is a variation of the sphere packing problem and is somehow related to the kissing number problem. For a dimension $n\ge 2$ and a natural $k$, let $r=r(n,k)$ be ...
0
votes
0answers
44 views

Bin Packing Algorithm and Minimal Area Axis-Aligned Bounding Boxes

I am a computer hobbyist and, just for the heck of it, I have decide to work on a bin packing algorithm. I would like for the program to eventually handle complex 2-D objects with bezier curves and ...
2
votes
0answers
197 views

Triangle Packing-Problem

Theory and Question We define a normalized triangle $T$ as an ordered list of six points s.t. $p \in [0,1)$ for all $p \in T$. Let $T = [x_0, y_0, x_1, y_1, x_2, y_2]$ be a normalized triangle. We ...
0
votes
0answers
64 views

3D Space Covering-Problem

Given a finite amount of "slots" in 3D space, e.g. $$S = [(1,2,3),(1,3,3),(1,4,3),(1,3,4)] \in \mathbb{N}^3.$$ I'm trying to find an efficient algorithm to determine a minimal set of (rectangular) ...
0
votes
0answers
84 views

calculate how many Ring can cut from a sheet

I am developing a software for a manufacturing company. My problem is , I need to find how many maximum rings can be cut from a sheet ( it can be rectangle or square sheet) And these rings ( with ...
0
votes
1answer
51 views

If you had a number of cubes of different sizes, what would be the algorithm to figure out the smallest cube they could fit in?

Is this possible to do, if so how would you do it? "If you had a number of cubes of different sizes, what would be the algorithm to figure out the smallest cube they could fit in?"
2
votes
0answers
102 views

A sphere packing problem

Suppose there is a large sphere of radius $R$. We want to pack it with smaller spheres. The volume of the smaller spheres change depending on where they are situated in the larger sphere. A smaller ...
7
votes
2answers
155 views

Unequal circles within circle with least possible radius?

It is the classical will-my-cables-fit-within-the-tube-problem which lead me to the interest of circle packing. So basically, I have 3 circles where r = 3 and 1 circle where r = 7 and I am trying to ...
1
vote
0answers
35 views

Number of touching triplets in hypersphere packing contact graph

I would like to know what is curently known about the number $N$ of touching-triplets involving a given vertex $V$ in the contact-graph of $d$-hypersphere packings. For $d=2$ and $d=3$, one has $N = ...
1
vote
0answers
96 views

Randomized packing of items

An adversary gives you a set of items whose total size is $x$ (he gets to choose how $x$ is distributed. e.g. there may be $k-1$ items of size $\frac{x}{k}$ and 2 items of size $\frac{x}{2k}$). The ...
1
vote
0answers
24 views

When does cubic packing of n^3 spheres in a cube break down (in terms of maximizing packing density)

Background: If you pack $n^2$ circles in a square, for 1, 4, 9, 16, 25, and 36 circles, the densest packing is with the circles stacked in an $n\times n$ grid. But for 49 circles the densest packing ...
6
votes
3answers
152 views

Finding the smallest sub-family of subsets needed to form a new subset

TL/DR I have a universe $U$ of items $u_i$ and a family $F$ of subsets of $U$ (call them $P_j$ ⊆ $U$). Given this family of subsets, I would like to find the sub-family $C$ ⊆ $F$ of subsets that can ...
5
votes
1answer
202 views

Does this packing problem even have an optimal solution?

Under this answer, user Bruno Joyal asks: This might be a naive question, but... how do we know there is a best possible solution? I (but that's just me) assume that he might be thinking of a ...
6
votes
1answer
111 views

Fair division of an octagon

A land-plot belongs to two partners. Its form is a regular octagon with area 1. They want to divide it such that one gets area $p$ and one gets area $1-p$, where $p \in (0,1)$ is a given constant. ...
2
votes
1answer
37 views

What is the first $w$ such that a rectangle, $R_{w\times w-1}$ is minimally-square-partitioned by less than $w$ squares.

Motivated by: Tiling an orthogonal polygon with squares, How to prove that the minimum square partition of a 3X2 rectangle has 3 squares, Minimum square partitions for 4x3 and 5x4 rectangles, What is ...
1
vote
0answers
23 views

“Sane” quantisation of moderate-dimensional analogue data

Warm-up problem (with solution): Suppose I have a measuring device that spits out a stream of real numbers, which I will model as i.i.d. random variables with range $\mathbb{R}$ and continuous ...
2
votes
1answer
186 views

Minimum square partitions for 4x3 and 5x4 rectangles

Motivation: Tiling an orthogonal polygon with squares Followup question: What is the first $w$ such that a rectangle, $R_{w\times w−1}$ is minimally-square-partitioned by less than $w$ squares.. Yes, ...
2
votes
2answers
133 views

Square covered with circles

I have a square 800x800 and i need to fully cover it with the least number of circles possible, each circle has a radius of 150. QUESTIONS: - What pattern would be the best to use? Clover, diamon or ...
18
votes
1answer
721 views

Why are these geometric problems so hard?

I was surprised to learn that both for the Moving Sofa Problem and Packing 11 Squares solutions have been proposed, but in either case the optimality of the proposed solution is, as of yet, only ...
1
vote
1answer
75 views

Combination of $2\times 1\times 1$ cubes inside a $3\times 3\times n$ cube

I came along this question in my math book and I can't seem to figure it out. I searched for packing problems, but i couldn't find the answer. You have a block with a width of $3$, depth of $3$ and a ...
0
votes
1answer
47 views

Goldilocks Packing type problem

This is a resource allocation problem I am attempting to formulate myself, so bear with me this isn't from the 12th edition of some math book. A miner is selecting 'rocks' from amongst his mine to ...
3
votes
1answer
106 views

Circle packing with a twist

A quick look at Wikipedia makes it quite clear that circle packing is an open question in mathematics, with only n<20 having efficient packings and many of those are merely conjectured. My ...
0
votes
1answer
82 views

Packingof Spheres in 3D

I am looking to find out the size of the largest sphere , that can fit in the voids created by packing spheres ( hcp) of radius R.
1
vote
1answer
2k views

How many circles of radius r fit in a single bigger circle of radius R?

Is there any formula to calculate how many circles of radius r fit in a single bigger circle of radius R? I'd apreciate if it didn't involve advanced math, like calculus (unless there is no other way, ...
3
votes
0answers
148 views

Fitting cubes inside a bigger cube

Suppose the sum of the volumes of $n$ cubes is 1. Then no matter what $n$ is I need to prove they can be put inside a cube of volume $\leq 2$ such that they do not overlap. I am totally going nuts ...
6
votes
1answer
803 views

The number of circles that will fit inside the area of larger circle?

Let's say circle $\omega_1$ has a diameter $X$. Let $X>Y$; $Y\in \mathbf{R}^{+}$. How many circles with diameter $Y$ will fit inside $\omega_1$? Is there a formula for this?
5
votes
0answers
171 views

Hexagonal circle packings in the plane

I have been reading the paper Spiral hexagonal circle packings in the plane (Alan F. Beardon, Tomasz Dubejko and Kenneth Stephenson, Geometriae Dedicata Volume 49, Issue 1, pp 39-70), which proves ...
0
votes
0answers
500 views

Packing rectangles in a grid

I have a problem that, discovered today, may be called "rectangle packing". I found extremely interesting references to papers in this question. But the rectangles I want to pack have dimensions that ...