New Approaches to Circle Packing in a Square
by Szabo, P. J.; Markot, M. Cs.; Csendes, T.; Specht, E.; Casado, L. G.Format: Hardcover
Pub. Date: 2006-12-15
Publisher(s): Springer Verlag
Other versions by this Author
List Price: $146.99
Rent Textbook
Select for Price
Rent Digital
$77.22
New Textbook
We're Sorry
Sold Out
Used Textbook
We're Sorry
Sold Out
How Marketplace Works:
- This item is offered by an independent seller and not shipped from our warehouse
- Item details like edition and cover design may differ from our description; see seller's comments before ordering.
- Sellers much confirm and ship within two business days; otherwise, the order will be cancelled and refunded.
- Marketplace purchases cannot be returned to eCampus.com. Contact the seller directly for inquiries; if no response within two days, contact customer service.
- Additional shipping costs apply to Marketplace purchases. Review shipping costs at checkout.
Summary
In one sense, the problem of finding the densest packing of congruent circles in a square is easy to understand. But on closer inspection, this problem reveals itself to be an interesting challenge of discrete and computational geometry with all its surprising structural forms and regularities. This book summarizes results achieved in solving the circle packing problem over the past few years, providing the reader with a comprehensive view of both theoretical and computational achievements. Typically illustrations of problem solutions are shown, elegantly displaying the results obtained.Beyond the theoretically challenging character of the problem, the solution methods developed in the book also have many practical applications.One especially important feature of the book is the inclusion on an enclosed CD of all the open source programming codes used. Since the codes can be worked with directly, they will enable the reader to improve on them and solve problem instances that still remain challenging, or to use them as a starting point for solving related application problems.
Table of Contents
| Preface | p. IX |
| Glossary of Symbols | p. XIII |
| Introduction and Problem History | p. 1 |
| Problem description and motivation | p. 1 |
| The history of circle packing | p. 2 |
| The problem of Malfatti | p. 2 |
| The circle packing studies of Farkas Bolyai | p. 2 |
| Packing problems from ancient Japan | p. 5 |
| A circle packing from Hieronymus Bosch | p. 6 |
| The densest packing of circles in the plane | p. 6 |
| Circle packings in bounded shapes | p. 7 |
| Generalizations and related problems | p. 8 |
| Packing of equal circles in a unit square | p. 8 |
| Problem Definitions and Formulations | p. 13 |
| Geometrical models | p. 13 |
| Mathematical programming models | p. 18 |
| Bounds for the Optimum Values | p. 23 |
| Lower bounds for the maximal distance m[subscript n] | p. 23 |
| Upper bounds for the optimal radius r[subscript n] | p. 25 |
| Asymptotic estimation and its error | p. 28 |
| Approximate Circle Packings Using Optimization Methods | p. 31 |
| An earlier approach: energy function minimization | p. 31 |
| The TAMSASS-PECS algorithm | p. 32 |
| Computational results | p. 37 |
| Other Methods for Finding Approximate Circle Packings | p. 43 |
| A deterministic approach based on LP-relaxation | p. 43 |
| A perturbation method | p. 44 |
| Billiard simulation | p. 44 |
| Pulsating Disk Shaking (PDS) algorithm | p. 45 |
| Computational results | p. 46 |
| Interval Methods for Validating Optimal Solutions | p. 51 |
| Problem formulation for the interval algorithms | p. 51 |
| Interval analysis | p. 53 |
| A prototype interval global optimization algorithm | p. 54 |
| An interval inclusion function for the objective function of the point arrangement problem | p. 56 |
| The subdivision step | p. 57 |
| Accelerating devices | p. 57 |
| The cutoff test | p. 58 |
| The 'method of active regions' | p. 58 |
| The First Fully Interval-based Optimization Method | p. 61 |
| A monotonicity test for the point arrangement problems | p. 61 |
| A special case of monotonicity-handling the free points | p. 63 |
| A rectangular approach for the 'method of active regions' | p. 65 |
| Numerical results | p. 68 |
| Local verification | p. 68 |
| Global solutions using tiles | p. 70 |
| The Improved Version of the Interval Optimization Method | p. 75 |
| Method of active regions using polygons | p. 76 |
| A new technique for eliminating tile combinations | p. 86 |
| Basic algorithms for the optimality proofs | p. 89 |
| An improved method for handling free points | p. 93 |
| Optimal packing of n = 28, 29, and 30 points | p. 95 |
| Hardware and software environment | p. 95 |
| The global procedure | p. 96 |
| Summary of the results for the advanced algorithm | p. 107 |
| Interval Methods for Verifying Structural Optimality | p. 109 |
| Packing structures and previous numerical results | p. 109 |
| Optimality and uniqueness properties | p. 111 |
| Repeated Patterns in Circle Packings | p. 115 |
| Finite pattern classes | p. 115 |
| The PAT(k[superscript 2] - l) (l = 0, 1, 2) pattern classes | p. 115 |
| The STR(k[superscript 2] - l) (l = 3, 4, 5) structure classes | p. 123 |
| The PAT(k(k + 1)) pattern class | p. 128 |
| The PAT(k[subscript 2] + [k/2]) pattern class | p. 128 |
| A conjectured infinite pattern class | p. 130 |
| Grid packings | p. 132 |
| Conjectural infinite grid packing sequences | p. 133 |
| Improved theoretical lower bounds based on pattern classes | p. 138 |
| Sharp, constant lower and upper bounds for the density of circle packing problems | p. 139 |
| Minimal Polynomials of Point Arrangements | p. 143 |
| Determining the minimal polynomial for a point arrangement | p. 143 |
| Optimal substructures | p. 144 |
| Examining the general case | p. 149 |
| Finding minimal polynomials using Maple | p. 153 |
| Determining exact values | p. 155 |
| Solving the P[subscript 11] (m) = 0 equation by radicals | p. 156 |
| Classifying circle packings based on minimal polynomials | p. 156 |
| The linear class | p. 158 |
| The quadratic class | p. 158 |
| The quartic class | p. 159 |
| Some classes with higher degree polynomials | p. 160 |
| About the Codes Used | p. 163 |
| The threshold accepting approach | p. 163 |
| Pulsating Disk Shaking | p. 166 |
| Installation | p. 166 |
| Why does the program use PostScript files? | p. 168 |
| Usage and command-line options | p. 168 |
| The interval branch-and-bound algorithm | p. 169 |
| Package components | p. 169 |
| Requirements | p. 171 |
| Installing and using circpack_1.3 | p. 172 |
| A Java demo program | p. 173 |
| Appendix A: Currently Best Known Results for Packing Congruent Circles in a Square | p. 179 |
| Numerical results for the packings | p. 179 |
| Figures of the packings | p. 179 |
| Bibliography | p. 219 |
| Related websites | p. 227 |
| List of Figures | p. 229 |
| List of Tables | p. 233 |
| Index | p. 237 |
| Table of Contents provided by Ingram. All Rights Reserved. |
An electronic version of this book is available through VitalSource.
This book is viewable on PC, Mac, iPhone, iPad, iPod Touch, and most smartphones.
By purchasing, you will be able to view this book online, as well as download it, for the chosen number of days.
Digital License
You are licensing a digital product for a set duration. Durations are set forth in the product description, with "Lifetime" typically meaning five (5) years of online access and permanent download to a supported device. All licenses are non-transferable.
More details can be found here.
A downloadable version of this book is available through the eCampus Reader or compatible Adobe readers.
Applications are available on iOS, Android, PC, Mac, and Windows Mobile platforms.
Please view the compatibility matrix prior to purchase.