Get 40% off our selection of bestselling print books in Engineering through October 31st!

Springer Optimization and Its Applications

New Approaches to Circle Packing in a Square

With Program Codes

Authors: Szabó, P.G., Markót, M.C., Csendes, T., Specht, E., Casado, L.G., García, I.

Buy this book

eBook $109.00
price for USA in USD (gross)
  • ISBN 978-0-387-45676-8
  • Digitally watermarked, DRM-free
  • Included format: PDF
  • ebooks can be used on all reading devices
  • Immediate eBook download after purchase
Hardcover $139.99
price for USA in USD
  • ISBN 978-0-387-45673-7
  • with online files
  • Free shipping for individuals worldwide
  • Usually dispatched within 3 to 5 business days.
Softcover $139.99
price for USA in USD
  • ISBN 978-1-4899-8897-3
  • Free shipping for individuals worldwide
  • Usually dispatched within 3 to 5 business days.
About this book

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.

Reviews

From the reviews:

"The book under review gives a detailed survey on the achievements of the last years on the problem of finding densest packings … . The text is written in a very comprehensive and informative way, and all the numerical results on densities are impressively illustrated by many figures of ‘optimal’ packings. … will serve as an excellent source for everybody, expert on non-expert, who is interested in circle packing or, who is just interested in the hardness of an appealing problem in discrete geometry." (Martin Henk, Zentralblatt MATH, Vol. 1128 (6), 2008)


Table of contents (12 chapters)

  • Introduction and Problem History

    Pages 1-11

  • Problem Definitions and Formulations

    Pages 13-21

  • Bounds for the Optimum Values

    Pages 23-29

  • Approximate Circle Packings Using Optimization Methods

    Pages 31-41

  • Other Methods for Finding Approximate Circle Packings

    Pages 43-49

Buy this book

eBook $109.00
price for USA in USD (gross)
  • ISBN 978-0-387-45676-8
  • Digitally watermarked, DRM-free
  • Included format: PDF
  • ebooks can be used on all reading devices
  • Immediate eBook download after purchase
Hardcover $139.99
price for USA in USD
  • ISBN 978-0-387-45673-7
  • with online files
  • Free shipping for individuals worldwide
  • Usually dispatched within 3 to 5 business days.
Softcover $139.99
price for USA in USD
  • ISBN 978-1-4899-8897-3
  • Free shipping for individuals worldwide
  • Usually dispatched within 3 to 5 business days.
Loading...

Recommended for you

Loading...

Bibliographic Information

Bibliographic Information
Book Title
New Approaches to Circle Packing in a Square
Book Subtitle
With Program Codes
Authors
Series Title
Springer Optimization and Its Applications
Series Volume
6
Copyright
2007
Publisher
Springer US
Copyright Holder
Springer-Verlag US
eBook ISBN
978-0-387-45676-8
DOI
10.1007/978-0-387-45676-8
Hardcover ISBN
978-0-387-45673-7
Softcover ISBN
978-1-4899-8897-3
Series ISSN
1931-6828
Edition Number
1
Number of Pages
XIV, 238
Topics