News for hackers. Stuff that matters.
Re:Erich's Packing Center by tshaddox on Sunday December 12, 2021 @01:20PM (#29532072)
I’ve encountered this lovely site several times over the years, but this is the first time I’ve noticed the animated section. These animations of circles are quite satisfying: https://erich-friedman.github.io/packing/ciranima/
Re:Erich's Packing Center by borepop on Sunday December 12, 2021 @04:10PM (#29533648)
My stepfather (a retired professor) is endlessly fascinated by these kinds of questions. If you ever ask him at dinner "so what are you working on?" the result is often a half-hour-long explanation of how many polygons could conceivably fit into some other polygon, if it's not about how many numbers could be derived from some other set of numbers. I've never been able to understand any of it, but it makes him happy.
Re:Erich's Packing Center by ptero on Sunday December 12, 2021 @08:51AM (#29529584)
This is a fascinating collection (especially in-depth plots of each type), thank you for posting (and many, many thanks to the author for building this)!
Re:Erich's Packing Center by pierrec on Sunday December 12, 2021 @04:06PM (#29533616)
I'm probably not the first one, but I wonder if there's a recognizable sequence in the "squares in triangles" packings: https://erich-friedman.github.io/packing/squintri/

You'll notice that some of the packings have a threefold rotational symmetry, but only for certain numbers of triangles: 3, 6, 9, 15, 27, 36... A quick search in OEIS yields cryptic results, probably a red herring.

Re:Erich's Packing Center by etaioinshrdlu on Sunday December 12, 2021 @04:23PM (#29533754)
I love this kind of stuff but am always searching for a good engineering application of it, and I can't think of too much. Anyone have some ideas?
Re:Erich's Packing Center by kwhitefoot on Sunday December 12, 2021 @04:48PM (#29533984)
It's not exactly the same but cutting shapes out of pieces of material in ways that waste as little as possible is surely related. The paper industry is very interested in a specialised subset of this kind of thing. So are factories that make transformer cores. The cores are made by stacking many (sometimes hundreds) of thin sheets of steel cut from rolls. Good quality core steel is expensive so it is important to waste as little as possible by making the cuts in the proper places.
Re:Erich's Packing Center by sidpatil on Sunday December 12, 2021 @05:08PM (#29534154)
These are specifically known as cutting stock problems [1].

Example of a possible application: I used to work at a home improvement retailer, and one of my responsibilities was to cut plywood boards for customers, to the dimensions they specified. I'd often wonder if the cuts I was making were optimal. The constraints were that any cuts I made had to go all the way through the entire piece, and that the blade itself was 1/8" thick.

[1] https://en.m.wikipedia.org/wiki/Cutting_stock_problem

Re:Erich's Packing Center by madcaptenor on Monday December 13, 2021 @10:21AM (#29540332)
A similar problem shows up in quilting - fabric comes in rolls of about 44 inches wide (called "WOF" for "width of fabric" in some patterns). (Occasionally there are other pieces - for example you can buy "fat quarters" which are 18 by 22 inches, i. e. half a yard by half WOF.) You may need many small pieces, say rectangles or triangles a few inches on a side. And so it's natural to ask what the best way to cut them is - either with minimal waste, or with making the smallest number of cuts.
Re:Erich's Packing Center by sidpatil on Sunday December 12, 2021 @04:58PM (#29534067)
Which field(s) of engineering did you have in mind?

One obvious application would be to find the minimum dimensions for a box to contain a number of identically-shaped physical parts. This would be a three-dimensional packing problem.

Another application could be to find out how to run the maximum number of VMs on a finite quantity of physical machines. This would be a multidimensional packing problem, possibly irregular since the VMs could have different memory, CPU, disk storage, etc. requirements.

Re:Erich's Packing Center by cycomanic on Sunday December 12, 2021 @05:06PM (#29534137)
Actually coding theory and modulation formats in communications are essentially very closely related to packing theory (in particular sphere packing)
Re:Erich's Packing Center by yumraj on Sunday December 12, 2021 @06:49PM (#29534932)
Amazon, or any other vendor for that matter, trying to figure out the smallest single box to ship all the items in your order using optimal packing material.
Re:Erich's Packing Center by PaulDavisThe1st on Sunday December 12, 2021 @08:16PM (#29535499)
It's seem abundantly clear from real world experience that even if they have an algorithmic method to determine this, it's only 1 input into the process. Hello, amzn shipping box that is 8x larger than the single content package.
Re:Erich's Packing Center by yumraj on Sunday December 12, 2021 @08:52PM (#29535681)
> it's only 1 input into the process

I'm sure you're right.. Other potential inputs are:

- availability of boxes and the type of packing material near the packer

- availability of space in the shipping container, so that it packs. This is again an application of the above concept. :)

- the item being shipped, fragile vs not so fragile and so on

- weight of the item, and how it fits in the container, similar to above

and so on.

Or, it is equally possible that currently there is no algorithm. the person packing just makes a judgement call :)

Re:Erich's Packing Center by madcaptenor on Monday December 13, 2021 @10:14AM (#29540273)
Here's how to fit twelve circular muffins on a circular plate: https://gottwurfelt.com/2020/12/27/applied-circle-packing-2/
Re:Erich's Packing Center by twic on Sunday December 12, 2021 @01:28PM (#29532152)
Who is Maurizio Morandi? He seems to have come up with a significant number of the most devious packings.
Re:Erich's Packing Center by eezurr on Sunday December 12, 2021 @01:30PM (#29532172)
This is lovely and made me smile. Reminds me of the (incredibly fun) times I spent on attempting to solve problems that wont necessarily have an impact on the real world (e.g. Collatz conjecture)