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

learn more… | top users | synonyms

0
votes
1answer
16 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 ...
10
votes
1answer
252 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
32 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 ...
0
votes
0answers
12 views

on-line Batched bin Packing

I have a project concerning "on-line Batched bin Packing" where the item sizes should be between 0 and 1 and have to be packed into bins of size 1. In my project I have to design a 3-batched online ...
2
votes
1answer
66 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
191 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
84 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
130 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
45 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
45 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 ...
30
votes
1answer
705 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
92 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
49 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$?
1
vote
1answer
88 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
35 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
153 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
56 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
63 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
42 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
69 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 ...
6
votes
2answers
120 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
32 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
90 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
23 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
147 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 ...
3
votes
1answer
164 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 ...
0
votes
0answers
36 views

How many spheres in the layer surrounding 12 spheres layer?

1 sphere is surrounded by 12 spheres(all identical). How many spheres in the layer surrounding above 12 spheres layer? I m not talking about $10n^2+2$. I mean a close fit to form a well enough ...
6
votes
1answer
99 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
36 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
22 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
165 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
115 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 ...
16
votes
1answer
643 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
68 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
0answers
61 views

The math behind packing problems

In my studies on algorithms, i landed on the three-dimensional packing problem. I'm trying to understand the math behind it. Given x,y,z of a rectangle q, what is the maximum number of q (optimal) ...
0
votes
1answer
43 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
86 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
81 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
958 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
107 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
0answers
590 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
139 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
371 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 ...
3
votes
2answers
246 views

Applonius Circle/ Ford Circle / Infinite GP / Circle Packing

All the smaller circles are mutually tangent and continue to infinity. What is sum of radii of all the smaller circles?
1
vote
0answers
44 views

Formulating square packing as a form of optimization

I was looking at square packing problem which is defined as: Given a number N... Find the smallest square that can pack N unit squares Each square can be associated with a 3 dimensional point ...
3
votes
1answer
120 views

rectangularizing the square

There is a square that I want to divide to n people, such that each person gets a rectangular piece with an equal area. An obvious option is to cut 1-by-n rectangles of size n-by-1, but the people ...
2
votes
1answer
116 views

Circle Packing: Unsolved Problem in Geometry?

Graham and Sloane minimize the second moment of the centres of a number discs in order to maximize their compactness. They use computational geometry techniques to find the optimal packings for ...
1
vote
1answer
49 views

Packing circles on a line

On today's TopCoder Single-Round Match, the following question was posed (the post-contest write-up hasn't arrived yet, and their explanations often leave much to be desired anyway, so I thought I'd ...
2
votes
1answer
57 views

Approximate radius of a group of n packed circles

I am looking for a formula to estimate the radius of a circle which would hold n number of circles with some radius r. I understand this is part of the packing problem which does not have a definite ...
20
votes
1answer
295 views

How many balls of radius 1 can be packed into a sphere of radius 10?

How I can calculate the maximum number of balls of radius 1 that can be packed into a sphere of radius 10?