Covering a Square with up to 30 Equal Circles

Reference:

Kari J. Nurmela and Patric R. J. Östergård. Covering a square with up to 30 equal circles. Research Report A62, Helsinki University of Technology, Laboratory for Theoretical Computer Science, Espoo, Finland, June 2000.

Abstract:

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

Suggested BibTeX entry:

@techreport{HUT-TCS-A62,
    address = {Espoo, Finland},
    author = {Kari J. Nurmela and Patric R. J. {\"O}sterg{\aa}rd},
    institution = {Helsinki University of Technology, Laboratory for Theoretical Computer Science},
    month = {June},
    number = {A62},
    pages = {14},
    title = {Covering a Square with up to 30 Equal Circles},
    type = {Research Report},
    year = {2000},
}