Application Center - Maplesoft

# Circle Packing in a Square

You can switch back to the summary page by clicking here.

Packing Circles in a Square of Minimum Size

 Introduction This application optimizes and visualizes the packing of circles (of varying radii) in a square, such that the side-length of the square is minimized.   One solution for 20 circles (with a radius of 1 to 20) is visualized below This is a difficult global optimization problem and demands strong solvers. This application uses Maple's Global Optimization Toolbox.   Circle packing (and packing optimization in general) is characterized by a large optimization space and many constraints; for this application, 20 circles generates 230 constraint equations.   The number of circles can be increased to create an increasingly complex problem; Maple automatically generates the symbolic constrain equations.   Applications like this are used to stress-test global optimizers.

Setup

 >

Number of circles

 >

Radius of circle i is equal to i

 >

Decision Variables and Optimization Bounds

The decision variables are the coordinates () of the centers of the circles, and the side length len of the circumscribing square.

 >
 >

Constraints

is the maximum distance from the origin to a point on the circumference of circle i

 >

is the distance between the centers of any two circles minus their radii

 >

The side-length of the square len must be greater than or equal to , for all circles. That is, the maximum distance between the furthest point on a circle's circumference and the origin must be smaller than the side length of the square (assuming the square is positioned on the origin)

 >

For circles i and j not to overlap,  must be zero or greater for all pairs of circles:

 >

Hence the entire set of constraints

 >
 (4.1)

Optimization and Results

 >
 (5.1)
 >
 (5.2)
 >
 >
 >
 >
 >
 >