From: Gerold Lee Gorman Subject: Re: Worst packing density Date: Tue, 14 Dec 1999 10:55:25 -0800 Newsgroups: sci.math To: Hauke Reddmann Keywords: convex shapes with worst packing density Hauke Reddmann wrote: > If you pack the plane with triangles or squares, > you have 0% waste. > If you pack it with circles...(forgot exact > number, too idle to compute) > Regular pentagons leave a lot of waste too. > Now which is the worst (convex) figure? > -- > Hauke Reddmann <:-EX8 BRANDNEW,IMPROVED SIG! > Send all spam to buggeth@thee.off > Send all personal e-mail to fc3a501@math.uni-hamburg.de > Send all e-mail for our chemistry workgroup to fc3a501@uni-hamburg.de Probably either pentagons or circles, my bet without doing any numbers at all is on pentagons, unless someone cares to refute this. Figuring that hexagons can be packed beehive like with 100% effeciency -- except for the edges. Anything higher will approach the effeciency of a circle as a limit, so that leaves the pentagon as the apparently most pathalogical choice. ============================================================================== From: "W Dudziak" Subject: Re: Worst packing density Date: Thu, 16 Dec 1999 19:54:36 -0600 Newsgroups: sci.math Triangles fit perfectly Squares fit perfectly Pentagons fit kinda nicely with only15.58% waste (semi dificult) Hexagons fit perfectly with 0% wasted space 7 gons fit badly with 36.38% waste (difficult) Octagons fit very well with only 17.157% wasted space (easily solved) Circles fit worst with a 21.46% waste (another easy solve) So, in conclusion: As far as i have calculated, 7gons have the worst packing density for your problem If you wish visuals for these, i can provide them easily. If you want an explaniation of how i solved, that may take me some time, but if you request, I'll try and make the time. - Will Dudziak, (www.dudziak.com) (will@dudziak.com) Gerold Lee Gorman wrote in message news:3856929D.8AF116B4@aol.com... [previous article quoted --djr] ============================================================================== From: kramsay@aol.commangled (Keith Ramsay) Subject: Re: Worst packing density Date: 18 Dec 1999 19:12:20 GMT Newsgroups: sci.math In article , "W Dudziak" writes: |Circles fit worst with a 21.46% waste |(another easy solve) Your waste ratio 21.46% is approximately 1-pi/4. You get 1-pi/4 waste if you arrange the circles in a square array, with each circle fitting a circumscribed square with area 4r^2. If you arrange the circles in a hexagonal array, each circle fits in a circumscribed hexagon which has area 2*sqrt(3), which gives a much more efficient packing (waste of 1-pi/2*sqrt(3) or approximately 9.31%). Keith Ramsay ============================================================================== From: Kurt Foster Subject: Re: Worst packing density Date: Tue, 14 Dec 1999 22:00:11 GMT Newsgroups: sci.math In <835jjt$ob1$1@rzsun03.rrz.uni-hamburg.de>, Hauke Reddmann said: . If you pack the plane with triangles or squares, you have 0% waste. . If you pack it with circles...(forgot exact number, too idle to compute) . Regular pentagons leave a lot of waste too. . Now which is the worst (convex) figure? I don't know. But even with closed and bounded convex regions of any shape at all, you can't force a lattice packing that wastes > 75% of the space. It's an easy argument: For a given region R of the type in question, let M be the maximum distance between any two points of the region. Let P and Q be two points of the region separated by distance M, and let L be the line through P and Q. Let D be the greatest distance, along any line perpendicular to L, between any two points of R, and let S and T be two points of R separated by distance D. Then the convex hull of P, Q, S and T has area M*D/2, so the area of R is >= M*D/2. On the other hand, the rectangle having sides of length M and 2D, and having its sides of length 2D bisected by P and Q, completely encloses the figure, and has area 2*M*D. So the figure takes up at least 1/4 of the area of the rectangle. Now, rectangles, each enclosing a duplicate of the original figure, can be packed in a lattice packing. ============================================================================== From: David G Radcliffe Subject: Re: Worst packing density Date: 16 Dec 1999 07:14:40 GMT Newsgroups: sci.math Hauke Reddmann wrote: : If you pack the plane with triangles or squares, : you have 0% waste. : If you pack it with circles...(forgot exact : number, too idle to compute) : Regular pentagons leave a lot of waste too. : Now which is the worst (convex) figure? I don't know the answer, but I found two reviews in Mathematical Reviews. I will summarize the relevant data from the first review, and quote the second review in its entirety (except that I trim the TeX notation). ----------------------------------------------------------------- 15,248b 52.0X Fejes Tóth, L. Lagerungen in der Ebene, auf der Kugel und im Raum. (German) Die Grundlehren der Mathematischen Wissenschaften, Band LXV. Springer-Verlag, Berlin-Göttingen-Heidelberg, 1953. x+197 pp. The density of the closest circle packing is pi/sqrt(12) ~= .9069, and the density of the closest lattice packing by regular octagons is 4(3-sqrt2)/7 ~= .9062. There is a "smoothed octagon" whose closest lattice packing has density (8-4sqrt2-ln2)/(2sqrt2-1) ~= .9024. [The review stated (9-4\surd 2-\log 2)/(2\surd 2-1)=.9024..., but the first 9 appears to be a typo.] ------------------------------------------------------------------ 87j:52020 52A45 Nazarov, F. L. On the Reinhardt problem of lattice packings of convex regions. Local extremality of the Reinhardt octagon. (Russian) Zap. Nauchn. Sem. Leningrad. Otdel. Mat. Inst. Steklov. (LOMI) 151 (1986), Issled. Teor. Chisel. 9, 104--114, 197--198. This paper concerns the well-known Reinhardt conjecture that, among all centrally symmetric plane convex sets M, the density delta(M) of the closest lattice packing is least for the so-called smoothed octagon M_0. Let Delta(M) denote the critical determinant of M. It is shown that there exists an epsilon>0 such that delta(M) <= \delta(M_0) for any centrally symmetric convex set M with M \subset (1+epsilon) M\sb 0 and \Delta(M)=\Delta(M\sb 0). Reviewed by Marek Lassak -- David Radcliffe radcliff@alpha2.csd.uwm.edu