Optimal set of rectangle sizes to pack arbitrary rectangle?
$begingroup$
I'm looking to build a set of wooden storage boxes of various standard sizes for storing small objects.
I would like to choose a set of "optimal" box sizes (outside dimensions) for filling arbitrary rectangular spaces.
I define "optimal" here as:
minimize wasted space after packing;
minimize different box sizes; and
minimize the number of boxes required to fill the space, assuming the definition of some largest box dimension.
In 1 dimension this is straightforward: a set of "boxes" of sizes { 16, 8, 4, 2, 1 } can fill any 1-dimensional space with less than 1 unit of waste with my definition of "optimal" as above.
For 2-dimensional spaces, I don't know how to solve this. It seems like there should be some geometric answer to this, but I'm not versed enough in packing problems to know where to start looking.
I was wondering if anybody on here could help solve this, or point the way to an answer?
Thanks!
geometry packing-problem
asked Jan 13 at 1:17
Shawn VincentShawn Vincent
1233
$endgroup$
add a comment |
$begingroup$
I'm looking to build a set of wooden storage boxes of various standard sizes for storing small objects.
I would like to choose a set of "optimal" box sizes (outside dimensions) for filling arbitrary rectangular spaces.
I define "optimal" here as:
minimize wasted space after packing;
minimize different box sizes; and
minimize the number of boxes required to fill the space, assuming the definition of some largest box dimension.
In 1 dimension this is straightforward: a set of "boxes" of sizes { 16, 8, 4, 2, 1 } can fill any 1-dimensional space with less than 1 unit of waste with my definition of "optimal" as above.
For 2-dimensional spaces, I don't know how to solve this. It seems like there should be some geometric answer to this, but I'm not versed enough in packing problems to know where to start looking.
I was wondering if anybody on here could help solve this, or point the way to an answer?
Thanks!
geometry packing-problem
asked Jan 13 at 1:17
Shawn VincentShawn Vincent
1233
$endgroup$
2
$begingroup$
Hi & welcome. I'm not sure if there is an answer for $2$ (or higher) dimensional spaces which will always simultaneously minimize all $3$ of your definitions for "optimal". If this is the case, can you rank your optimal requirements from most to least important?
$endgroup$
– John Omielan
Jan 13 at 1:41
$begingroup$
Excellent question. I'd say, in order, they'd be: (1 - most important) minimize wasted space, (2) minimize distinct box sizes, (3) minimize number of boxes to fill space. Thanks!
$endgroup$
– Shawn Vincent
Jan 14 at 2:50
add a comment |
$begingroup$
I'm looking to build a set of wooden storage boxes of various standard sizes for storing small objects.
I would like to choose a set of "optimal" box sizes (outside dimensions) for filling arbitrary rectangular spaces.
I define "optimal" here as:
minimize wasted space after packing;
minimize different box sizes; and
minimize the number of boxes required to fill the space, assuming the definition of some largest box dimension.
In 1 dimension this is straightforward: a set of "boxes" of sizes { 16, 8, 4, 2, 1 } can fill any 1-dimensional space with less than 1 unit of waste with my definition of "optimal" as above.
For 2-dimensional spaces, I don't know how to solve this. It seems like there should be some geometric answer to this, but I'm not versed enough in packing problems to know where to start looking.
I was wondering if anybody on here could help solve this, or point the way to an answer?
Thanks!
geometry packing-problem
asked Jan 13 at 1:17
Shawn VincentShawn Vincent
1233
$endgroup$
I'm looking to build a set of wooden storage boxes of various standard sizes for storing small objects.
I would like to choose a set of "optimal" box sizes (outside dimensions) for filling arbitrary rectangular spaces.
I define "optimal" here as:
minimize wasted space after packing;
minimize different box sizes; and
minimize the number of boxes required to fill the space, assuming the definition of some largest box dimension.
In 1 dimension this is straightforward: a set of "boxes" of sizes { 16, 8, 4, 2, 1 } can fill any 1-dimensional space with less than 1 unit of waste with my definition of "optimal" as above.
For 2-dimensional spaces, I don't know how to solve this. It seems like there should be some geometric answer to this, but I'm not versed enough in packing problems to know where to start looking.
I was wondering if anybody on here could help solve this, or point the way to an answer?
Thanks!
geometry packing-problem
geometry packing-problem
asked Jan 13 at 1:17
Shawn VincentShawn Vincent
1233
asked Jan 13 at 1:17
Shawn VincentShawn Vincent
1233
asked Jan 13 at 1:17
Shawn VincentShawn Vincent
1233
asked Jan 13 at 1:17
Shawn VincentShawn Vincent
1233
asked Jan 13 at 1:17
Shawn VincentShawn Vincent
1233
1233
2
$begingroup$
Hi & welcome. I'm not sure if there is an answer for $2$ (or higher) dimensional spaces which will always simultaneously minimize all $3$ of your definitions for "optimal". If this is the case, can you rank your optimal requirements from most to least important?
$endgroup$
– John Omielan
Jan 13 at 1:41
$begingroup$
Excellent question. I'd say, in order, they'd be: (1 - most important) minimize wasted space, (2) minimize distinct box sizes, (3) minimize number of boxes to fill space. Thanks!
$endgroup$
– Shawn Vincent
Jan 14 at 2:50
add a comment |
2
$begingroup$
Hi & welcome. I'm not sure if there is an answer for $2$ (or higher) dimensional spaces which will always simultaneously minimize all $3$ of your definitions for "optimal". If this is the case, can you rank your optimal requirements from most to least important?
$endgroup$
– John Omielan
Jan 13 at 1:41
$begingroup$
Excellent question. I'd say, in order, they'd be: (1 - most important) minimize wasted space, (2) minimize distinct box sizes, (3) minimize number of boxes to fill space. Thanks!
$endgroup$
– Shawn Vincent
Jan 14 at 2:50
2
2
$begingroup$
Hi & welcome. I'm not sure if there is an answer for $2$ (or higher) dimensional spaces which will always simultaneously minimize all $3$ of your definitions for "optimal". If this is the case, can you rank your optimal requirements from most to least important?
$endgroup$
– John Omielan
Jan 13 at 1:41
$begingroup$
Hi & welcome. I'm not sure if there is an answer for $2$ (or higher) dimensional spaces which will always simultaneously minimize all $3$ of your definitions for "optimal". If this is the case, can you rank your optimal requirements from most to least important?
$endgroup$
– John Omielan
Jan 13 at 1:41
$begingroup$
Excellent question. I'd say, in order, they'd be: (1 - most important) minimize wasted space, (2) minimize distinct box sizes, (3) minimize number of boxes to fill space. Thanks!
$endgroup$
– Shawn Vincent
Jan 14 at 2:50
$begingroup$
Excellent question. I'd say, in order, they'd be: (1 - most important) minimize wasted space, (2) minimize distinct box sizes, (3) minimize number of boxes to fill space. Thanks!
$endgroup$
– Shawn Vincent
Jan 14 at 2:50
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
I'm not sure if this is optimal, but it works.
My collection optimises "no wasted space", and it also minimises the number of boxes required in the sense that "the most efficient tiling of any space" is obtained by using the biggest boxes first. However, you may feel that there are too many boxes.
For $2$-dimensional space, I use $(x,y)$ to denote rectangles with side lengths $x$ and $y$.
${(1,1), (1,2), (1,2), (2,2)}$ will fill all spaces (with integer sides) up to $3times 3$ with no gaps (with the greedy algorithm)
${(1,1),(1,2),(1,2),(1,4),(1,4),(2,2),(2,4),(2,4),(4,4)}$ will fill all spaces with integer sides up to $7times 7$ with no gaps (with the greedy algorithm)
More generally, the collections of boxes are defined by:
one of each box of size $(x,x)$,
two of each box of size $(x,y)$ with $xneq y$, where $x,y in {1,2,4,8,...}$.
I conjecture that the collection of boxes generated in this way will always tile larger 2d spaces with no gaps using the greedy algorithm. (I have verified this for the two cases above, but not for e.g. $15times 15$, $31times 31$,...)
By "using the greedy algorithm", I mean that if you attempt to tile some space, you just have to start with the biggest box, then use the second biggest box, etc.
I suspect that there maybe a more optimal solution which makes use of golden-ratio-eqsue maths.
answered Jan 14 at 2:04
HarambeHarambe
6,06821843
$endgroup$
add a comment |
$begingroup$
Although you don't need all the properties of this particular partition
based on triangular numbers, you
might consider using it, or an analogous partition:
Image from Wikipedia.
answered Jan 14 at 1:32
Joseph O'RourkeJoseph O'Rourke
18.2k350113
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3071605%2foptimal-set-of-rectangle-sizes-to-pack-arbitrary-rectangle%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
I'm not sure if this is optimal, but it works.
My collection optimises "no wasted space", and it also minimises the number of boxes required in the sense that "the most efficient tiling of any space" is obtained by using the biggest boxes first. However, you may feel that there are too many boxes.
For $2$-dimensional space, I use $(x,y)$ to denote rectangles with side lengths $x$ and $y$.
${(1,1), (1,2), (1,2), (2,2)}$ will fill all spaces (with integer sides) up to $3times 3$ with no gaps (with the greedy algorithm)
${(1,1),(1,2),(1,2),(1,4),(1,4),(2,2),(2,4),(2,4),(4,4)}$ will fill all spaces with integer sides up to $7times 7$ with no gaps (with the greedy algorithm)
More generally, the collections of boxes are defined by:
one of each box of size $(x,x)$,
two of each box of size $(x,y)$ with $xneq y$, where $x,y in {1,2,4,8,...}$.
I conjecture that the collection of boxes generated in this way will always tile larger 2d spaces with no gaps using the greedy algorithm. (I have verified this for the two cases above, but not for e.g. $15times 15$, $31times 31$,...)
By "using the greedy algorithm", I mean that if you attempt to tile some space, you just have to start with the biggest box, then use the second biggest box, etc.
I suspect that there maybe a more optimal solution which makes use of golden-ratio-eqsue maths.
answered Jan 14 at 2:04
HarambeHarambe
6,06821843
$endgroup$
add a comment |
$begingroup$
I'm not sure if this is optimal, but it works.
My collection optimises "no wasted space", and it also minimises the number of boxes required in the sense that "the most efficient tiling of any space" is obtained by using the biggest boxes first. However, you may feel that there are too many boxes.
For $2$-dimensional space, I use $(x,y)$ to denote rectangles with side lengths $x$ and $y$.
${(1,1), (1,2), (1,2), (2,2)}$ will fill all spaces (with integer sides) up to $3times 3$ with no gaps (with the greedy algorithm)
${(1,1),(1,2),(1,2),(1,4),(1,4),(2,2),(2,4),(2,4),(4,4)}$ will fill all spaces with integer sides up to $7times 7$ with no gaps (with the greedy algorithm)
More generally, the collections of boxes are defined by:
one of each box of size $(x,x)$,
two of each box of size $(x,y)$ with $xneq y$, where $x,y in {1,2,4,8,...}$.
I conjecture that the collection of boxes generated in this way will always tile larger 2d spaces with no gaps using the greedy algorithm. (I have verified this for the two cases above, but not for e.g. $15times 15$, $31times 31$,...)
By "using the greedy algorithm", I mean that if you attempt to tile some space, you just have to start with the biggest box, then use the second biggest box, etc.
I suspect that there maybe a more optimal solution which makes use of golden-ratio-eqsue maths.
answered Jan 14 at 2:04
HarambeHarambe
6,06821843
$endgroup$
add a comment |
$begingroup$
I'm not sure if this is optimal, but it works.
My collection optimises "no wasted space", and it also minimises the number of boxes required in the sense that "the most efficient tiling of any space" is obtained by using the biggest boxes first. However, you may feel that there are too many boxes.
For $2$-dimensional space, I use $(x,y)$ to denote rectangles with side lengths $x$ and $y$.
${(1,1), (1,2), (1,2), (2,2)}$ will fill all spaces (with integer sides) up to $3times 3$ with no gaps (with the greedy algorithm)
${(1,1),(1,2),(1,2),(1,4),(1,4),(2,2),(2,4),(2,4),(4,4)}$ will fill all spaces with integer sides up to $7times 7$ with no gaps (with the greedy algorithm)
More generally, the collections of boxes are defined by:
one of each box of size $(x,x)$,
two of each box of size $(x,y)$ with $xneq y$, where $x,y in {1,2,4,8,...}$.
I conjecture that the collection of boxes generated in this way will always tile larger 2d spaces with no gaps using the greedy algorithm. (I have verified this for the two cases above, but not for e.g. $15times 15$, $31times 31$,...)
By "using the greedy algorithm", I mean that if you attempt to tile some space, you just have to start with the biggest box, then use the second biggest box, etc.
I suspect that there maybe a more optimal solution which makes use of golden-ratio-eqsue maths.
answered Jan 14 at 2:04
HarambeHarambe
6,06821843
$endgroup$
I'm not sure if this is optimal, but it works.
My collection optimises "no wasted space", and it also minimises the number of boxes required in the sense that "the most efficient tiling of any space" is obtained by using the biggest boxes first. However, you may feel that there are too many boxes.
For $2$-dimensional space, I use $(x,y)$ to denote rectangles with side lengths $x$ and $y$.
${(1,1), (1,2), (1,2), (2,2)}$ will fill all spaces (with integer sides) up to $3times 3$ with no gaps (with the greedy algorithm)
${(1,1),(1,2),(1,2),(1,4),(1,4),(2,2),(2,4),(2,4),(4,4)}$ will fill all spaces with integer sides up to $7times 7$ with no gaps (with the greedy algorithm)
More generally, the collections of boxes are defined by:
one of each box of size $(x,x)$,
two of each box of size $(x,y)$ with $xneq y$, where $x,y in {1,2,4,8,...}$.
I conjecture that the collection of boxes generated in this way will always tile larger 2d spaces with no gaps using the greedy algorithm. (I have verified this for the two cases above, but not for e.g. $15times 15$, $31times 31$,...)
By "using the greedy algorithm", I mean that if you attempt to tile some space, you just have to start with the biggest box, then use the second biggest box, etc.
I suspect that there maybe a more optimal solution which makes use of golden-ratio-eqsue maths.
answered Jan 14 at 2:04
HarambeHarambe
6,06821843
answered Jan 14 at 2:04
HarambeHarambe
6,06821843
answered Jan 14 at 2:04
HarambeHarambe
6,06821843
answered Jan 14 at 2:04
HarambeHarambe
6,06821843
6,06821843
add a comment |
add a comment |
$begingroup$
Although you don't need all the properties of this particular partition
based on triangular numbers, you
might consider using it, or an analogous partition:
Image from Wikipedia.
answered Jan 14 at 1:32
Joseph O'RourkeJoseph O'Rourke
18.2k350113
$endgroup$
add a comment |
$begingroup$
Although you don't need all the properties of this particular partition
based on triangular numbers, you
might consider using it, or an analogous partition:
Image from Wikipedia.
answered Jan 14 at 1:32
Joseph O'RourkeJoseph O'Rourke
18.2k350113
$endgroup$
add a comment |
$begingroup$
Although you don't need all the properties of this particular partition
based on triangular numbers, you
might consider using it, or an analogous partition:
Image from Wikipedia.
answered Jan 14 at 1:32
Joseph O'RourkeJoseph O'Rourke
18.2k350113
$endgroup$
Although you don't need all the properties of this particular partition
based on triangular numbers, you
might consider using it, or an analogous partition:
Image from Wikipedia.
answered Jan 14 at 1:32
Joseph O'RourkeJoseph O'Rourke
18.2k350113
answered Jan 14 at 1:32
Joseph O'RourkeJoseph O'Rourke
18.2k350113
answered Jan 14 at 1:32
Joseph O'RourkeJoseph O'Rourke
18.2k350113
answered Jan 14 at 1:32
Joseph O'RourkeJoseph O'Rourke
18.2k350113
18.2k350113
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3071605%2foptimal-set-of-rectangle-sizes-to-pack-arbitrary-rectangle%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
2
$begingroup$
Hi & welcome. I'm not sure if there is an answer for $2$ (or higher) dimensional spaces which will always simultaneously minimize all $3$ of your definitions for "optimal". If this is the case, can you rank your optimal requirements from most to least important?
$endgroup$
– John Omielan
Jan 13 at 1:41
$begingroup$
Excellent question. I'd say, in order, they'd be: (1 - most important) minimize wasted space, (2) minimize distinct box sizes, (3) minimize number of boxes to fill space. Thanks!
$endgroup$
– Shawn Vincent
Jan 14 at 2:50