Notice bibliographique
- Notice
Type(s) de contenu et mode(s) de consultation : Texte noté : électronique
Auteur(s) : Szabó, Péter Gábor
Markót, Mihály Csaba (1979- ...)
Csendes, Tibor
Markót, M. Cs
Csendes, T
Specht, E
Casado, L. G.
García, I
Titre(s) : New Approaches to Circle Packing in a Square [Texte électronique] : With Program Codes / by P.G. Szabó, ... M. Cs. Markót, ... T. Csendes ... [et al.]
Publication : Boston, MA : Springer US : Springer e-books, 2007
Description matérielle : 1 online resource
Collection : Mathematics and Statistics (Springer-11649)
Springer Optimization and Its Applications ; 6
Note(s) : Titre provenant de la page de titre du document numérisé. - Numérisation de l'édition de New York : Springer, cop. 2007. - Bibliogr. Index
Fichier PDF.
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 two-dimensional 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
hard-to-solve 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.
Audience This 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 high-dimensional nonlinear optimization problems with nonlinear constraints
Sujet(s) : Géométrie discrète -- Informatique
Empilements de cercles -- Informatique
Indice(s) Dewey :
519.6 (23e éd.) = Optimisation mathématique
Identifiants, prix et caractéristiques : ISBN 9780387456768
Identifiant de la notice : ark:/12148/cb446427489
Notice n° :
FRBNF44642748
(notice reprise d'un réservoir extérieur)
