The Pursuit of Perfect Packing www.com The Pursuit of Perfect Packing Tomaso Aste Istituto Nazionale per la Fisica della Materia, Genoa, Italy and Denis Weaire Trinity College, Dublin, Ireland Institute of Physics Publishing Bristol and Philadelphia www.com c IOP Publishing Ltd 2000 All rights reserved. No part of this publication may be reproduced, stored in a retrieval system or transmitted in any form or by any means, electronic, mechanical, photocopying, recording or otherwise, without the prior permission of the publisher. Multiple copying is permitted in accordance with the terms of licences issued by the Copyright Licensing Agency under the terms of its agreement with the Committee of Vice-Chancellors and Principals. British Library Cataloguing-in-Publication Data A catalogue record for this book is available from the British Library.
ISBN 0 7503 0648 3 pbk 0 7503 0647 5 hbk Library of Congress Cataloging-in-Publication Data are available Publisher: Nicki Dennis Commissioning Editor: Jim Revill Production Editor: Simon Laurenson Production Control: Sarah Plenty Cover Design: Victoria Le Billon Marketing Executive: Colin Fenton Published by Institute of Physics Publishing, wholly owned by The Institute of Physics, London Institute of Physics Publishing, Dirac House, Temple Back, Bristol BS1 6BE, UK US Office: Institute of Physics Publishing, The Public Ledger Building, Suite 1035, 150 South Independence Mall West, Philadelphia, PA 19106, USA Typeset in TEX using the IOP Bookmaker Macros Printed in the UK by J W Arrowsmith Ltd, Bristol www.com Dedicated by TA to Nicoletta www.com Contents Preface xi 1 How many sweets in the jar? 1 2 Loose change and tight packing 5 2.1 A handful of coins 5 2.2 When equal shares are best 6 2.3 Regular and semi-regular packings 11 2.4 Disordered, quasi-ordered and fractal packings 13 2.5 The Voronoı̈ construction 16 3 Hard problems with hard spheres 20 3.1 The greengrocer’s dilemma 20 3.2 Balls in bags 20 3.3 A new way of looking 22 3.4 How many balls in the bag? 24 3.5 Osborne Reynolds: a footprint on the sand 24 3.6 Ordered loose packings 27 3.7 Ordered close packing 27 3.8 The Kepler Conjecture 29 3.9 Marvellous clarity: the life of Kepler 32 3.10 Progress by leaps and bounds? 34 4 Proof positive? 35 4.1 News from the Western Front 35 4.2 The programme of Thomas Hales 37 4.5 The problem of proof 43 4.6 The power of thought 44 www.com viii Contents 5 Peas and pips 45 5.4 The improbable seed 48 5.5 Biological cells, lead shot and soap bubbles 50 6 Enthusiastic admiration: the honeycomb 54 6.1 The honeycomb problem 54 6.2 What the bees do not know 56 7 Toils and troubles with bubbles 59 7.1 Playing with bubbles 59 7.2 A blind man in the kingdom of the sighted 60 7.4 Foam and ether 65 7.5 The Kelvin cell 68 7.6 The twinkling of an eye 70 7.8 A discovery in Dublin 72 8 The architecture of the world of atoms 75 8.2 Atoms and molecules: begging the question 77 8.3 Atoms as points 78 8.10 Crystal nonsense 90 9 Apollonius and concrete 91 9.3 Packing fraction and fractal dimension 94 9.4 Packing fraction in granular aggregate 95 10 The Giant’s Causeway 97 10.2 Idealization oversteps again 98 10.3 The first official report 99 10.6 Lost city? 102 www.com Contents ix 11 Soccer balls, golf balls and buckyballs 103 11.5 The Thomson problem 107 11.6 The Tammes problem 108 11.7 Helical packings 110 12 Packings and kisses in high dimensions 113 12.1 Packing in many dimensions 113 12.3 More kisses 117 13 Odds and ends 119 13.6 Dodecahedral packing and curved spaces 124 13.7 The Malfatti problem 125 13.8 Microspheres and opals 126 13.9 Order from shaking 127 13.11 Turning down the heat: simulated annealing 130 14 Conclusion 133 Index 134 www.com Preface There are many things which might be packed into a book about packing. Our choice has been eclectic. Around the mathematical core of the subject we have gathered examples from far and wide. It was difficult to decide how to handle references.
This is not intended as a heavyweight monograph or an all-inclusive handbook, but the reader may well wish to check or pursue particular topics. We have tried to give a broad range of general references to authoritative books and review articles. In addition we have identified the original source of many of the key results which are discussed, together with enough clues in the text to enable other points to be followed up, for example with a biographical dictionary. Thanks are due to many colleagues who have helped us, including Nicolas Rivier (a constant source of stimulation and esoteric knowledge), Stefan Hutzler and Robert Phelan.
Rob Kusner and Jörg Wills made several suggestions for the text, which we have adopted. Denis Weaire benefited from the research support of Enterprise Ireland and Shell during the period in which this was written, and Tomaso Aste was a Marie Curie Research Fellow of the EU during part of it. Tomaso Aste Denis Weaire December 1999 xi www.com Chapter 1 How many sweets in the jar? The half-empty suitcase or refrigerator is a rare phenomenon. We seem to spend much of our lives squeezing things into tight spaces, and scratching our heads when we fail.
The poet might have said: packing and stacking we lay waste our days. To the designer of circuit boards or software the challenge carries a stimu- lating commercial reward: savings can be made by packing things well. How can we best go about it, and how do we know when the optimal solution has been found? This has long been a teasing problem for the mathematical fraternity, one in which their delicate webs of formal argument somehow fail to capture much cer- tain knowledge. Their frustration is not shared by the computer scientist, whose more rough-and-ready tactics have found many practical results.
Physicists also take an interest, being concerned with how things fit together in nature. And many biologists have not been able to resist the temptation to look for a geometrical story to account for the complexities of life itself. So our account of packing problems will range from atoms to honeycombs in search of inspiration and applications. Unless engaged in smuggling, we are likely to pack our suitcase with mis- cellaneous items of varying shape and size.
This compounds the problem of how to arrange them. The mathematician would prefer to consider identical objects, and an infinite suitcase. How then can oranges be packed most tightly, if we do not have to worry about the container? This is a celebrated question, associated with the name of one of the greatest figures in the history of science, Johannes Kepler, and highlighted by David Hilbert at the start of the 20th century.com 2 How many sweets in the jar? Figure 1. Stacking casks of Guinness.
Hilbert’s 18th problem In 1900, David Hilbert presented to the International Mathematical Congress in Paris a list of 23 problems which he hoped would guide math- ematical research in the 20th century. The 18th problem was concerned with sphere packing and space-filling polyhedra. I point out the following question (. ) important to number theory and perhaps sometimes useful to physics and chemistry: How one can arrange most densely in space an infinite number of equal solids of given form, e.
spheres with given radii or regular tetrahedra with given edges (or in prescribed positions), that is, how can one so fit them together that the ratio of the filled to the unfilled space may be as great as possible? www.com How many sweets in the jar? 3 Figure 1. Packing on a grand scale: Wright T 1750 The Cosmos. More subtle goals than that of maximum density may be invoked. When bubbles are packed tightly to form a foam, as in a glass of beer, they can adjust their shapes and they do so to minimize their surface area.
So in this case, the total volume is fixed and it is the total area of the interfaces between the bubbles that is minimized. The history of ideas about packing is peopled by many eminent and colourful characters. An English reverend gentlemen is remembered for his experiments in squashing peas together in the pursuit of geometrical insights. A blind Belgian scientist performed by proxy the experiments that laid the ground rules for serious play with bubbles.
An Irishman of unrivalled reputation for dalliance (at least www.com 4 How many sweets in the jar? among crystallographers) gave us the rules for the random packing of balls. A Scotsman who was the grand old man of Victorian science was briefly obsessed with the parsimonious partitioning of space. All of them shared the curiosity of the child at the church bazaar: how many sweets are there in the jar? www.com Chapter 2 Loose change and tight packing 2.1 A handful of coins An ample handful of loose change, spread out on a table, will help us understand some of the principles of packing. This will serve to introduce some of the basic notations of the subject, before we tackle the complexity of three dimensions and the obscurities of higher dimensions.
Let us discard the odd-shaped coins which are becoming fashionable; we want hard circular discs. Coins come in various sizes, so let us further simplify the problem by selecting a set of equal size. About ten will do. The question is: how could a large number of these coins be arranged most tightly? If we do it in three-dimensional space, then obviously the well known bank- roll is best for any number of coins.
But here we restrict ourselves to two- dimensional packing on the flat surface of the table. Three coins fit neatly together in a triangle, as in figure 2. There is no difficulty in continuing this strategy, with each coin eventually contacting six neighbours. A pleasant pattern soon emerges: the triangular close packing in two dimensions.
The fraction of table covered by coins is called the packing fraction, which is = Area covered = p = 0:9068 : : : : (2.1) Total area 12 This must surely be the largest possible value. But can we prove it? That is often where the trouble starts, but not in this case. A proof can be constructed as follows.com 6 Loose change and tight packing (a) (b) (c) Figure 2. Three equal discs fit tightly in an equilateral triangle (a).
This configuration can be extended to generate the triangular close packing (b). This is the densest possible arrangement of equal discs, having packing fraction = 0:9068 : : :. The regular pattern drawn by joining the centres of touching discs is the triangular lattice (c).2 When equal shares are best There is a general principle which helps with many packing problems: it says that, under certain circumstances, equal shares are best. (We shall resist any www.com When equal shares are best 7 Figure 2.
What is the best price for two fields, of a total area of 40 hectares? temptation to draw moral lessons for politicians at this point.) A parable will serve to illustrate this principle in action. A farmer, attracted by certain European subsidies, seeks to purchase two fields with a total area of 40 hectares. The prices for fields depend on the field size as shown in the diagram of figure 2. What is he to do? Playing with the different possibilities quickly convinces him that he should buy two fields of 20 hectares each.
The combination of ten and 30 hectares is more expensive; its price is twice that indicated by the open circle on the diagram, which lies above the price of a 20 hectare field. What property of the price structure forces him to choose equal-sized fields? It is the upward curvature of figure 2.2, which we may call convexity.