Research Report A62: Covering a Square with up to 30 Equal Circles

Author: Kari J. Nurmela and Patric R. J. Östergård

Date: June 2000

Pages: 14

A computational method for finding good coverings of a square with equal circles is presented. The algorithm uses a quasi-Newton method with BFGS secant update to minimize the uncovered area by moving the circles. The radius of the circles is further adapted to find locally optimal coverings, and the algorithm is applied repeatedly to random initial configurations. The structures of the coverings are determined and the coordinates of each circle are calculated with high precision using a mathematical model for an idealized physical structure consisting of tensioned bars and frictionless pin joints. Best found coverings of a square with up to 30 circles are displayed, 17 of which are new or improve on earlier published coverings.

Keywords: circle covering, equidistant graph, square

Full report in Postscript