imported>Klbrain: /* Proposed merge with Nesting algorithm */ Closing; no merge

2025-04-02T16:48:02Z

Proposed merge with Nesting algorithm: Closing; no merge

New page

{{WikiProject banner shell|class=C|
{{WikiProject Mathematics|priority=Mid }}
}}

== VfD results ==

This article was nominated for deletion. The result was '''no consensus''', but some merging/redirecting might be in order. For details, please see [[Wikipedia:Votes for deletion/MoreKarlScherer]]. --[[User:BD2412| BD2412]] [[User talk:BD2412|talk]] 00:36, July 14, 2005 (UTC)

This article was nominated for deletion a second time, this time kept outright, See [[Wikipedia:Votes for deletion/KarlSchererRevisited1]]. [[User:Sjakkalle|Sjakkalle]] [[User talk:Sjakkalle|(Check!)]] 09:16, 27 July 2005 (UTC)

== Dubious-ness ==

Could someone with a large (by number of edits, not by time) edit history (so that it is obviously not Karl Scherer or friends) verify the maths examples in this article. They strike me as inaccurate and/or non-noteworthy and/or presented with [[Wikipedia:Weasel words|Weasel words]]

[[User:-Ril-|<nowiki>~~</nowiki><nowiki>~~</nowiki>]] 21:15, 20 July 2005 (UTC)

:Why are you disputing these? Weren't they there a long time ago? [[User:Charles Matthews|Charles Matthews]] 10:05, 27 July 2005 (UTC)

Correct me if I'm wrong,

:Maybe I did not find the best packing but the first box I could put an extra disc is 2x238 after that each extra 238 gives me extra two balls...

This is very different from numbers in the article, could anyone provide a ref? [[User:Tosha|Tosha]] 23:24, 18 October 2005 (UTC)

== Fiction? in article ==

I am a Maths Graduate and teacher, and yet I cannot see any possible way to pack more than 2n circles in an n X 2cm strip. To do so, essentially you would have either fit more circles (or part circles) vertically (there's no room) or horizontally. To benefit from hexagonal packing you would have to have a wider strip, and hexagonal packing is the most efficient way of packing circles. Furthermore, the article talks about a classic problem, and yet that problem is not mentioned [http://mathworld.wolfram.com/CirclePacking.html on this article in Math World about circle packing].

As citations were asked for a long time ago, and have not been provided, I will now change the article and remove contentious references (they can be restored if citations are found).

[[User:Captainj|Captainj]] 17:29, 22 May 2006 (UTC)

::OK, I think I can posted the answer to your problem. Stand by... [[User:Michael Hardy|Michael Hardy]] 20:15, 22 May 2006 (UTC)

[[Image:Packing.png]]

Maybe I'll return to this later. For now I'll just suggest thinking about how many circles in the figure above should be "centered" and how many should not be. [[User:Michael Hardy|Michael Hardy]] 20:38, 22 May 2006 (UTC)

I still can't make this work. If we use the packing method in the picture, and have 2 circles (in a vertical line) followed by a centered circle followed by another two circles, you get a total area of 3.92 for the five circles. The length of the strip that they occupy is <math>1 + \sqrt(5) \approx 6.47</math>. This means the area of the strip they occupy is approximately 8.47, giving an efficiency of 60.7%%. But the "standard efficiency" (all the circles two "neat" lines) is 78.5%. Therefore every time a centered circle is but between two standard packed circles, you lose area. So there doesn't seem to be any benefit in doing it that way.

If the circles were only put at then end, this wouldn't help either, because, in any case, the length of the strip is an integer.

Sorry I haven't drawn all the diagrams etc, but I don't have the software to do it easily. (I did all the working out back of the envelope). I hope my above Maths is correct, its clear I am going rusty in places.[[User:Captainj|Captainj]] 21:28, 22 May 2006 (UTC)

:You can do better than this. First lay a layer on the bottom. Then lay a layer above it, touching it, but offset by half a ball. Now notice that there is a gap at the top. Therefore this whole structure can be zigzagged a bit to compact it.[[User:99of9|99of9]] ([[User talk:99of9|talk]]) 02:01, 1 September 2009 (UTC)

:: So you can pack two rows of circles whose diameter is a bit greater than half the width of the strip; that's an answer to a question other than what was asked here, I think. —[[User:Tamfang|Tamfang]] ([[User talk:Tamfang|talk]]) 02:49, 1 September 2009 (UTC)

::: Well I meant you could zigzag the bottom row a bit (and the top row would still fit), increasing the lineal density, rather than expanding the circles. --[[User:99of9|99of9]] ([[User talk:99of9|talk]]) 05:52, 10 May 2010 (UTC)

:::: How does that increase the density? —[[User:Tamfang|Tamfang]] ([[User talk:Tamfang|talk]]) 16:37, 10 May 2010 (UTC)

:::::Easier to explain with an image. I'm impressed that you're still watching the page - I almost didn't bother replying when I saw how long it had been! --[[User:99of9|99of9]] ([[User talk:99of9|talk]]) 00:26, 11 May 2010 (UTC)

:::::[[Image:Circle-strip.svg|frameless|500px|Packing on a strip with density 1.006046496.]]

:::::: Ah! —[[User:Tamfang|Tamfang]] ([[User talk:Tamfang|talk]]) 02:46, 11 May 2010 (UTC)
:::::: Well, you've convinced me. But it should really still be sourced. — Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[User:Captainj|Captainj]] ([[User talk:Captainj|talk]] • [[Special:Contributions/Captainj|contribs]]) 23:16, 4 January 2012 (UTC) 
::::::: That's easy. [http://www.math.uiuc.edu/~z-furedi/PUBS/furedi_circles-in-a-strip.pdf See Fig. 1.2 (c) on page 4 of the PDF] [[User:Leob|Leob]] ([[User talk:Leob|talk]]) 21:05, 11 March 2016 (UTC)

== Walter Stromquist ==

Where did the fact about Walter Stromquist proving something come from? I can't find it in the sources given. [[User:Leon math|Leon math]] 23:44, 14 December 2006 (UTC)

== Other known results ==

Not a single reference or proof for any of these. —Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/84.92.32.151|84.92.32.151]] ([[User talk:84.92.32.151|talk]]) 21:09, 26 November 2007 (UTC) 
===balls inside a ball?===
After noticing some interest at the RD/M I have added a short description about the case of packing few balls into a ball (of whom I don't have references)... I thought it could be nice to have a complete description of an easy packing problem. NOw I wonder if maybe it should better be shortened...--[[User:PMajer|pma]] ([[User talk:PMajer|talk]]) 09:12, 30 April 2009 (UTC)

== de Bruijn's theorem: neccessary condition? ==

De Brujin's theorem, as stated,
<blockquote>
de Bruijn's theorem: A box can be packed with a harmonic brick a × a b × a b c if the box has dimensions a p × a b q × a b c r for some natural numbers p, q, r (i.e., the box is a multiple of the brick.)
</blockquote>
is obvious. Perhaps what is really meant is "if and only if?" —Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/92.193.118.17|92.193.118.17]] ([[User talk:92.193.118.17|talk]]) 09:59, 4 October 2009 (UTC) 

== "Klarner's" theorem ==

The article says:

:[[Klarner's theorem]]: An ''a'' × ''b'' rectangle can be packed with 1 × ''n'' strips iff ''n'' | ''a'' or ''n'' | ''b''.

No cite is given for the name "Klarner's theorem". Is "Klarner" [[David A. Klarner]]?

I added a citation of this theorem: {{cite journal|last1=Wagon|first1=Stan|title=Fourteen Proofs of a Result About Tiling a Rectangle|journal=[[The American Mathematical Monthly]]|year=1987|month=August-September|volume=94|issue=7|page=601–617|url=http://mathdl.maa.org/images/upload_library/22/Ford/Wagon601-617.pdf|accessdate=6 Jan 2010}}. But Wagon does not refer to the theorem as Klarner's; he cites it as a special case of a theorem of [[N. G. de Bruijn]] which may be the [[de Bruijn's theorem]] mentioned in this wikipedia article just after "Klarner's".

({{Mathworld|urlname=KlarnersTheorem|title=Klarner's Theorem}}) cites to a book by Ross Honsberger. Can someone confirm that this book really calls the theorem "Klarner's"? Or is this just another Mathworld oddity?

—[[User:Dominus|Dominus]] ([[User talk:Dominus|talk]]) 16:19, 6 January 2010 (UTC)

:The cited source ({{cite book | title = Mathematical Gems II | last1 = Honsberger | first1 = Ross | year = 1976 | DUPLICATE_isbn = | publisher = [[The Mathematical Association of America]] | isbn = 0-88385-302-7 | page = 67 }}) does not bear out the attribution. Honsberger credits Klarner, but does not refer to the result as "Klarner's theorem". I think this is a Mathworld neologism. Klarner is indeed David A. Klarner. Honsberger's cite is: {{cite journal | title = Uniformly coloured stained glass windows | journal = Proceedings of the London Mathematical Society |series = 3 | issue = 23 | pages = 613–628 | last1 = Klarner | first1 = D.A. | last2 = Hautus | first2 = M.L.J | year = 1971 }} —[[User:Dominus|Mark Dominus]] ([[User talk:Dominus|talk]]) 07:16, 5 January 2012 (UTC)

== Same problem in 3D ==

Does wikipedia have any references to this same problem in 3d, and for arbitrary shapes?

Is there any algorithm to solve these problems, other than just "try all possibilities"? [[Special:Contributions/87.194.84.113|87.194.84.113]] ([[User talk:87.194.84.113|talk]]) 23:35, 9 May 2010 (UTC)
:[[Tetrahedron packing]] is one article I know of. I know a lot about binary sphere packing (in Euclidean space), but haven't written anything for wiki. What shapes are you interested in? --[[User:99of9|99of9]] ([[User talk:99of9|talk]]) 05:54, 10 May 2010 (UTC)

== Rectangle Packing ==

This section is particularly sparse, and only talks about one special case. Could it possibly be fleshed out?[[User:Samineru|Samineru]] ([[User talk:Samineru|talk]]) 22:01, 1 March 2011 (UTC)

== No techniques, no proofs ==

I believe the topic is important to have a wiki article on.
I also believe the implementation is unsatisfactory in part because: 1) no word in it of how the packings
presented were found;2) how they were proven (if at all).
Both items, especially, 2 are hard to present fully and they may be connected. (The article has some names of people
who prove optimalitry of some packings).
I would not expect any complete description on these,
but no word at all... that is too much
to not have (or too little to have) in a good article.
As to how some of the packings were found, I may suggest
an item
on which I've just written a wiki article [[Lubachevsky-Stillinger algorithm]]. This is certainly not the only one in existence, so go ahead and put a list of other
techniques.
But, as a matter of fact, I know that many of the
optimal (proven or conjectured) packings,
e.g., of 91 congruent circles in a circle, were found first
with this very algorithm (and then confirmed
with other algorithms, which is usually much easier,
than to discover; some recent proof techniques are ''based'' on knowing the packing with high precision,
so discovering the packing numerically becomes, essentially, a first step of the proof). See
Curved Hexagonal Packings of Equal Disks in a Circle
http://www.math.ucsd.edu/~ronspubs/95_02_dense_packings.pdf
It was also fun to read a comment and its resolution
above on packing more than
2n unit diam circles in 2 times n rectangles.
That problem was one of many by [[Erdos]]. Does this article
mention that name? Yes, but not emphatically
enough for a math genius of the 20th century.
(Remember ''notability'' requirement of wiki).
The mentioned above algorithm produces
the required packings (for some smaller n of course).
If I remember it correctly, for n=1000 you can exceed
2n by 7.

[[User:Lsalgo|Lsalgo]] ([[User talk:Lsalgo|talk]]) 04:18, 23 May 2011 (UTC)

== Finite uniform 3D sphere packing ==

There does not seem to be any discussion of uniform 3D sphere packing on the English Wikipedia; as "sited" [http://math.stackexchange.com/a/186316/820#comment430415_186316 here] it is only discussed on the German Wikipedia [[:de:Theorie der endlichen Kugelpackungen|here]], even though there is an English summary of research as of 1999 by [[John Conway|Conway]] and [[Neil Sloane|Sloane]] [http://books.google.com.au/books?id=upYwZ6cQumoC&pg=PR24&lpg=PR24&dq=55+sphere+sausage+-site:wikipedia.org&source=bl&ots=_L-VYTk7wX&sig=vGLfnGxTsM_lFaS8Zuz-chdZa2c&hl=en#v=onepage&q=55%20sphere%20sausage%20-site%3Awikipedia.org&f=false here]. [[User:Markhurd|Mark Hurd]] ([[User talk:Markhurd|talk]]) 07:54, 28 August 2012 (UTC)

: [[Sphere packing]]? [[Close-packing of equal spheres]]? —[[User:Tamfang|Tamfang]] ([[User talk:Tamfang|talk]]) 08:01, 28 August 2012 (UTC)
:: Yeah "not ... any" is a little strong. Specifically nothing seems to mention the "sausage collapse" after 55 spheres. [[User:Markhurd|Mark Hurd]] ([[User talk:Markhurd|talk]]) 13:00, 28 August 2012 (UTC)

== unequal-sphere dimmers ==

What is '''unequal-sphere dimmer'''? Where I can read about it? [[User:Jumpow|Jumpow]] ([[User talk:Jumpow|talk]]) 13:11, 8 June 2016 (UTC)

May be it is misspelling and must be '''[[dimer]]'''? [[User:Jumpow|Jumpow]] ([[User talk:Jumpow|talk]]) 14:45, 8 June 2016 (UTC)

Again, what means '''woodpulp stowage''' in context of packing of a single rectangle?
Woodpulp refers to article [[Pulp (paper)]]: ''Pulp is a lignocellulosic fibrous material prepared by chemically or mechanically separating cellulose fibres from wood, fiber crops or waste paper''. [[User:Jumpow|Jumpow]] ([[User talk:Jumpow|talk]]) 16:31, 8 June 2016 (UTC)

What means '''pack one of each n-omino into a rectangle'''? Pack set of n-omino into a single rectangle (each only ones)? Into given single rectangle? Into minimal single rectangle? Not all n-omino? [[User:Jumpow|Jumpow]] ([[User talk:Jumpow|talk]]) 17:12, 8 June 2016 (UTC)

== Is the puzzle template appropriate? ==

The first line of the article reads

"Packing problems are a class of optimization problems in mathematics that involve attempting to pack objects together into containers."

Given the technical nature of the article, is it appropriate to have a template with links such as [[Optical illusion]] and [[Thinking outside the box]]?

[[Special:Contributions/104.228.101.152|104.228.101.152]] ([[User talk:104.228.101.152|talk]]) 05:04, 16 March 2017 (UTC)

==Untitled==
O(a7/11) is not consistent with Wikipedia's other pages. It changed several decades ago. Thanks Paul Erdös — Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/1.136.109.183|1.136.109.183]] ([[User talk:1.136.109.183#top|talk]]) 09:22, 20 October 2021 (UTC) 

== Proposed merge with [[Nesting algorithm]] ==

[[User:The Anome]] has proposed that this article and [[Nesting algorithm]] be merged, but without starting any discussion with a rationale for the merge. I think this merge is a bad idea and I '''oppose the merge'''. The articles are related, but with so different a focus as to make any merged article schizophrenic and confusing to all audiences. The [[packing problems]] article is mainly focused on packing identical objects into a simple shape, viewed as a problem in pure or recreational mathematics although it does have a very brief paragraph on "Packing of irregular objects" mostly saying that it is not really amenable to the mathematical approach. The [[nesting algorithm]] article is instead focused on packing problems of irregular objects as a practical and computational problem with industrial applications, describing heuristics that have been designed to provide practical solutions with little interest in what can be proven mathematically (because very little can be proven mathematically). Beyond being on a topic that is superficially the same they have very little overlap in content. [[Nesting algorithm]] has much more in common with [[Cutting stock problem]] than it does with this article. —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 07:36, 12 March 2025 (UTC)
:'''Closing''', given that there was no case made and a clear objection. [[User:Klbrain|Klbrain]] ([[User talk:Klbrain|talk]]) 16:48, 2 April 2025 (UTC)

Talk:Packing problems - Revision history

imported>Klbrain: /* Proposed merge with Nesting algorithm */ Closing; no merge