Description 
1 online resource (xiv, 238 pages) : illustrations 
Series 
Springer optimization and its applications ; v. 6 

Springer optimization and its applications ; v. 6.

Contents 
Preface  Glossary of Symbols  1. Introduction and Problem History  2. Problem Definitions and Formulations  3. Bounds for the Optimum Values  4. Approximate Circle Packings Using Optimization Methods  5. Other Methods for Finding Approximate Circle Packings  6. Interval Methods for Validating Optimal Solutions  7. The First Fully Intervalbased Optimization Method  8. The Improved Version of the Interval Optimization Method  9. Interval Methods for Verifying Structural Optimality  10. Repeated Patterns in Circle Packings  11. Minimal Polynomials of Point Arrangements  12. About the Codes Used  Appendix A. Currently Best Known Results for Packing Congruent Circles in a Square  Bibliography  Related Web Sites  List of Figures  List of Tables  Index 
Summary 
In one sense, the problem of finding the densest packing of congruent circles in a square is easy to understand: it is a matter of positioning a given number of equal circles in such a way that the circles fit fully in a square without overlapping. 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. As the number of circles to be packed increases, solving a circle packing problem rapidly becomes rather difficult. To give an example of the difficulty of some problems, consider that in several cases there even exists a circle in an optimal packing that can be moved slightly while retaining the optimality. Such free circles (or "rattles") mean that there exist not only a continuum of optimal solutions, but the measure of the set of optimal solutions is positive! 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. Direct applications include cutting out congruent twodimensional objects from an expensive material, or locating points within a square in such a way that the shortest distance between them is maximal. Circle packing problems are closely related to the "obnoxious facility location" problems, to the Tammes problem, and less closely related to the Kissing Number Problem. The emerging computational algorithms can also be helpful in other hardtosolve optimization problems like molecule conformation. The wider scientific community has already been involved in checking the codes and has helped in having the computational proofs accepted. 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. AudienceThis book will appeal to those interested in discrete geometrical problems and their efficient solution techniques. Operations research and optimization experts will also find it worth reading as a case study of how the utilization of the problem structure and specialities made it possible to find verified solutions of previously hopeless highdimensional nonlinear optimization problems with nonlinear constraints 
Bibliography 
Includes bibliographical references (pages 219225) and index 
Notes 
English 

Print version record 
In 
Springer ebooks 
Subject 
Circle packing  Data processing


Discrete geometry  Data processing


MATHEMATICS  Geometry  General.


CírculoCuadratura  DatosTratamiento


Discrete geometry  Data processing


Packung Mathematik


Kreis


Pakking (natuurwetenschappen)


Cirkels.


Numerieke wiskunde.

Form 
Electronic book

Author 
Szabó, P. G. (Péter Gábor)

ISBN 
9780387456768 

0387456767 

0387456732 

9780387456737 

6610901449 

9786610901449 
