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

learn more… | top users | synonyms

0
votes
2answers
37 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 ...
2
votes
0answers
26 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?
0
votes
2answers
72 views

Problem solving with letter sequences

I've been through some passed exam questions and came across this one: (1) How to find out how many 5 letter sequences are possible that use the letters m, a, t, h, s once each? (2) How to find out ...
0
votes
1answer
39 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
30 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
60 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
23 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
122 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
48 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
48 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
30 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
55 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
101 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
22 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
71 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 ...
6
votes
3answers
141 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
127 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
34 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 ...
4
votes
1answer
82 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
31 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
21 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
151 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
101 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 ...
15
votes
1answer
602 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
64 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
53 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
39 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
76 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
680 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
89 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 ...
7
votes
0answers
500 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?
4
votes
0answers
117 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
319 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 ...
0
votes
0answers
91 views

Rectangles in polygon - packing problem

I see a lot of packing problems focusing on covering the smallest amount of space with a given number of rectangles, but I'm trying to solve the inverse problem - I have polygon A with given vertices. ...
3
votes
2answers
211 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?
0
votes
0answers
112 views

Packing irregular shape with regular shape

What is approach/algorithm to pack an irregular/regular shape with fixed size regular shapes/objects. In the case below, we packed an arbitrary irregular shape with three circles of fixed radius.
0
votes
0answers
35 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
114 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
104 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
45 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 ...
20
votes
1answer
260 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?
1
vote
1answer
170 views

Is there an optimized version of rectangle packing algorithm?

I have a rectangle with 200 width and 100 height. I have a mix pool of 50 rectangles and boxes. The rectangles comes in shapes like 20x40, and 40x20. The boxes will come in shapes of 20x20 and 40x40. ...
0
votes
1answer
209 views

Find coordinates of n points uniformly distributed in a rectangle

I have a rectangle R of width W and height H. I have N points inside this rectangle. I need to find an algorithm to position my points in the rectangle in the most uniform way possible (no overlaps, ...
0
votes
0answers
892 views

2d bin packing problem, with opportunity to optimize the size of the bin

I have been tasked with optimizing a manufacturing process. It is a non-trivial, NP hard problem. The problem is similar to the 2d bin packing problem, but we are trying to optimize the size of the ...
1
vote
1answer
111 views

What is the relative behaviour when a center circle surrounded by 6 circles is (recursively) replaced by 6 circles

Start with a given "inner" circle of arbitrary radius (blue) centered at C. Surround it by 6 circles of equal radius. This concerns to known issues of circle packing and is a frequently treated ...
0
votes
1answer
65 views

number of overlaps in sphere covering

I have a problem and I'm hoping someone can point me in the right direction. I have the following conjecture: For a set of spheres of arbitrary radii in $\mathbb{R}^d$, in which the center point of ...
4
votes
1answer
112 views

Packing three squares into an equilateral triangle

I am trying to pack 3 equal, largest possible sized squares into an equilateral triangle.
0
votes
0answers
72 views

Optimal packing for a box layout

I am not mathematically inclined enough to express this question rigorously, but it certainly sounds like a problem for mathematics. I was making a cutout from a piece of cardboard to make a box with ...
1
vote
1answer
93 views

Smallest Circle that encircles $4$ circles

I want to calculate the radius of the smallest circle (radius $R$) that can hold $4$ circles (with radii $a, b, c, d$) inside it, such that: No circles overlaps one other. $a \ge b \ge c \ge d.$ ...
0
votes
1answer
77 views

What is the minimum of squares to fit within rectangular box 10 x 16?

I'm trying to apply circle packing data to a 10 x 16 inch sheet for printing, here: http://hydra.nat.uni-magdeburg.de/packing/csq/csq.html#Applications And I want to achieve the least waste by ...