Interval methods for verifying structural optimality of circle packing configurations in the unit square

The paper is dealing with the problem of finding the densest packings of equal circles in the unit square. Recently, a global optimization method based exclusively on interval arithmetic calculations has been designed for this problem. With this method it became possible to solve the previously open...

Full description

Saved in:
Bibliographic Details
Published in:Journal of computational and applied mathematics 2007-02, Vol.199 (2), p.353-357
Main Author: MARKET, Mihaly Csaba
Format: Article
Language:English
Subjects:
Applied sciences
Circle packing
Computer-assisted proof
Convex and discrete geometry
Error analysis
Exact sciences and technology
Geometry
Interval analysis
Mathematical programming
Mathematics
Numerical analysis
Numerical analysis. Scientific computation
Operational research and scientific management
Operational research. Management science
Sciences and techniques of general use
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The paper is dealing with the problem of finding the densest packings of equal circles in the unit square. Recently, a global optimization method based exclusively on interval arithmetic calculations has been designed for this problem. With this method it became possible to solve the previously open problems of packing 28, 29, and 30 circles in the numerical sense: tight guaranteed enclosures were given for all the optimal solutions and for the optimum value. The present paper completes the optimality proofs for these cases by determining all the optimal solutions in the geometric sense. Namely, it is proved that the currently best-known packing structures result in optimal packings, and moreover, apart from symmetric configurations and the movement of well-identified free circles, these are the only optimal packings. The required statements are verified with mathematical rigor using interval arithmetic tools.
ISSN:0377-0427
1879-1778
DOI:10.1016/j.cam.2005.08.039