A Literature Review on Circle and Sphere Packing Problems: Models and Methodologies
---
paper_title: Maximin Latin Hypercube Designs in Two Dimensions

paper_content:

The problem of finding a maximin Latin hypercube design in two dimensions can be described as positioning n non-attacking rooks on an n x n chessboard such that the minimal distance between pairs of rooks is maximized.Maximin Latin hypercube designs are important for the approximation and optimization of black box functions.In this paper general formulas are derived for maximin Latin hypercube designs for general n, when the distance measure is l8 or l1. Furthermore, for the distance measure l2 we obtain maximin Latin hypercube designs for n = 70 and approximate maximin Latin hypercube designs for the values of n.We show the reduction in the maximin distance caused by imposing the Latin hypercube design structure is small.This justifies the use of maximin Latin hypercube designs instead of unrestricted designs.(This abstract was borrowed from another version of this item.)
---
paper_title: A simulated annealing approach for the circular cutting problem

paper_content:

We propose a heuristic for the constrained and the unconstrained circular cutting problem based upon simulated annealing. We define an energy function, the small values of which provide a good concentration of the circular pieces on the left bottom corner of the initial rectangle. Such values of the energy correspond to configurations where pieces are placed in the rectangle without overlapping. Appropriate software has been devised and computational results and comparisons with some other algorithms are also provided and discussed. � 2003 Elsevier B.V. All rights reserved.
---
paper_title: Minimum perimeter rectangles that enclose congruent non-overlapping circles

paper_content:

We use computational experiments to find the rectangles of minimum perimeter into which a given number n of non-overlapping congruent circles can be packed. No assumption is made on the shape of the rectangles. In many of the packings found, the circles form the usual regular square-grid or hexagonal patterns or their hybrids. However, for most values of n in the tested range n =< 5000, e.g., for n = 7, 13, 17, 21, 22, 26, 31, 37, 38, 41, 43...,4997, 4998, 4999, 5000, we prove that the optimum cannot possibly be achieved by such regular arrangements. Usually, the irregularities in the best packings found for such n are small, localized modifications to regular patterns; those irregularities are usually easy to predict. Yet for some such irregular n, the best packings found show substantial, extended irregularities which we did not anticipate. In the range we explored carefully, the optimal packings were substantially irregular only for n of the form n = k(k+1)+1, k = 3, 4, 5, 6, 7, i.e., for n = 13, 21, 31, 43, and 57. Also, we prove that the height-to-width ratio of rectangles of minimum perimeter containing packings of n congruent circles tends to 1 as n tends to infinity.
---
paper_title: Dense packings of congruent circles in rectangles with a variable aspect ratio

paper_content:

We use computational experiments to find the rectangles of minimum area into which a given number n of non-overlapping congruent circles can be packed. No assumption is made on the shape of the rectangles. Most of the packings found have the usual regular square or hexagonal pattern. However, for 1495 values of n in the tested range n≤ 5000, specifically, for n = 49, 61, 79, 97, 107, …4999, we prove that the optimum cannot possibly be achieved by such regular arrangements.The evidence suggests that the limiting height-to-width ratio of rectangles containing an optimal hexagonal packing of circles tends to \( 2 - \sqrt 3 \) as n → ∞, if the limit exists.
---
paper_title: Improving Dense Packings of Equal Disks in a Square

paper_content:

We describe a new numerical procedure for generating dense packings of disks and spheres inside various geometric shapes. We believe that in some of the smaller cases, these packings are in fact optimal. When applied to the previously studied cases of packing n equal disks in a square, the procedure confirms all the previous record packings except for n = 32, 37, 48, and 50 disks, where better packings than those previously recorded are found. For n = 32 and 48, the new packings are minor variations of the previous record packings. However, for n = 37 and 50, the new patterns differ substantially. For example, they are mirror-symmetric, while the previous record packings are not.
---
paper_title: An improved typology of cutting and packing problems

paper_content:

The number of publications in the area of Cutting and Packing (C&P) has increased considerably over the last two decades. The typology of C&P problems introduced by Dyckhoff [Dyckhoff, H., 1990. A typology of cutting and packing problems. European Journal of Operational Research 44, 145–159] initially provided an excellent instrument for the organisation and categorisation of existing and new literature. However, over the years also some deficiencies of this typology became evident, which created problems in dealing with recent developments and prevented it from being accepted more generally. In this paper, the authors present an improved typology, which is partially based on Dyckhoff’s original ideas, but introduces new categorisation criteria, which define problem categories different from those of Dyckhoff. Furthermore, a new, consistent system of names is suggested for these problem categories. Finally, the practicability of the new scheme is demonstrated by using it as a basis for a categorisation of the C&P literature from the years between 1995 and 2004. � 2006 Elsevier B.V. All rights reserved.
---
paper_title: A simulated annealing approach for the circular cutting problem

paper_content:

We propose a heuristic for the constrained and the unconstrained circular cutting problem based upon simulated annealing. We define an energy function, the small values of which provide a good concentration of the circular pieces on the left bottom corner of the initial rectangle. Such values of the energy correspond to configurations where pieces are placed in the rectangle without overlapping. Appropriate software has been devised and computational results and comparisons with some other algorithms are also provided and discussed. � 2003 Elsevier B.V. All rights reserved.
---
paper_title: Packing up to 50 Equal Circles in a Square

paper_content:

The problem of maximizing the radius of n equal circles that can be packed into a given square is a well-known geometrical problem. An equivalent problem is to find the largest distance d, such that n points can be placed into the square with all mutual distances at least d. Recently, all optimal packings of at most 20 circles in a square were exactly determined. In this paper, computational methods to find good packings of more than 20 circles are discussed. The best packings found with up to 50 circles are displayed. A new packing of 49 circles settles the proof that when n is a square number, the best packing is the square lattice exactly when n≤ 36.
---
paper_title: Extremal problems for convex polygons

paper_content:

Consider a convex polygon V n with n sides, perimeter P n , diameter D n , area A n , sum of distances between vertices S n and width W n . Minimizing or maximizing any of these quantities while fixing another defines 10 pairs of extremal polygon problems (one of which usually has a trivial solution or no solution at all). We survey research on these problems, which uses geometrical reasoning increasingly complemented by global optimization methods. Numerous open problems are mentioned, as well as series of test problems for global optimization and non-linear programming codes.
---
paper_title: A New Verified Optimization Technique for the "Packing Circles in a Unit Square" Problems

paper_content:

This paper presents a new verified optimization method for the problem of finding the densest packings of nonoverlapping equal circles in a square. In order to provide reliable numerical results, the developed algorithm is based on interval analysis. As one of the most efficient parts of the algorithm, an interval-based version of a previous elimination procedure is introduced. This method represents the remaining areas still of interest as polygons fully calculated in a reliable way. Currently the most promising strategy of finding optimal circle packing configurations is to partition the original problem into subproblems. Still, as a result of the highly increasing number of subproblems, earlier computer-aided methods were not able to solve problem instances where the number of circles was greater than 27. The present paper provides a carefully developed technique resolving this difficulty by eliminating large groups of subproblems together. As a demonstration of the capabilities of the new algorithm the problems of packing 28, 29, and 30 circles were solved within very tight tolerance values. Our verified procedure decreased the uncertainty in the location of the optimal packings by more than 700 orders of magnitude in all cases.
---
paper_title: New results in the packing of equal circles in a square

paper_content:

Abstract The problem of finding the maximum diameter of n equal mutually disjoint circles inside a unit square is addressed in this paper. Exact solutions exist for only n = 1, …, 9,10,16,25,36 while for other n only conjectural solutions have been reported. In this work a max-min optimization approach is introduced which matches the best reported solutions in the literature for all n ⩽ 30, yields a better configuration for n = 15, and provides new results for n = 28 and 29.
---
paper_title: Dense packings of equal disks in an equilateral triangle: from 22 to 34 and beyond

paper_content:

Previously published packings of equal disks in an equilateral triangle have dealt with up to 21 disks. We use a new discrete-event simulation algorithm to produce packings for up to 34 disks. For each n in the range 22 ≤ n ≤ 34 we present what we believe to be the densest possible packing of n equal disks in an equilateral triangle. For these n we also list the second, often the third and sometimes the fourth best packings among those that we found. In each case, the structure of the packing implies that the minimum distance d(n) between disk centers is the root of polynomial Pn with integer coefficients. In most cases we do not explicitly compute Pn but in all cases we do compute and report d(n) to 15 significant decimal digits. Disk packings in equilateral triangles differ from those in squares or circles in that for triangles there are an infinite number of values of n for which the exact value of d(n) is known, namely, when n is of the form ∆(k) := k(k+1) 2 . It has also been conjectured that d(n−1) = d(n) in this case. Based on our computations, we present conjectured optimal packings for seven other infinite classes of n, namely
---
paper_title: An improved algorithm for the packing of unequal circles within a larger containing circle

paper_content:

Abstract This paper describes an approved algorithm for the problems of unequal circle packing – the quasi-physical quasi-human algorithm. First, the quasi-physical approach for the general packing problems is described in solving the pure problems of unequal circle packing. The method is an analogy to the physical model in which a number of smooth cylinders are packed inside a container. A quasi-human strategy is then proposed to trigger a jump for a stuck object in order to get out of local minima. Our method has been tested in numerical experiments. The computational results are presented, showing the merits of the proposed method. Our algorithm can be thought as an adoptive algorithm of the Tabu search.
---
paper_title: A beam search algorithm for the circular packing problem

paper_content:

In this paper, we propose to solve the circular packing problem (CPP) whose objective is to pack n different circles C"i of known radius r"i,[email protected]?N={1,...,n}, into the smallest containing circle C. The objective is to determine the radius r of C as well as the coordinates (x"i,y"i) of the center of the packed circles C"i,[email protected]?N. CPP is solved by using an adaptive beam search algorithm that combines the beam search, the local position distance and the dichotomous search strategy. Decisions at each node of the developed tree are based on the well-known maximum hole degree that uses the local minimum distance. The computational results, on a set of instances taken from the literature, show the effectiveness of the proposed algorithm.
---
paper_title: An improved typology of cutting and packing problems

paper_content:

The number of publications in the area of Cutting and Packing (C&P) has increased considerably over the last two decades. The typology of C&P problems introduced by Dyckhoff [Dyckhoff, H., 1990. A typology of cutting and packing problems. European Journal of Operational Research 44, 145–159] initially provided an excellent instrument for the organisation and categorisation of existing and new literature. However, over the years also some deficiencies of this typology became evident, which created problems in dealing with recent developments and prevented it from being accepted more generally. In this paper, the authors present an improved typology, which is partially based on Dyckhoff’s original ideas, but introduces new categorisation criteria, which define problem categories different from those of Dyckhoff. Furthermore, a new, consistent system of names is suggested for these problem categories. Finally, the practicability of the new scheme is demonstrated by using it as a basis for a categorisation of the C&P literature from the years between 1995 and 2004. � 2006 Elsevier B.V. All rights reserved.
---
paper_title: Solving circle packing problems by global optimization: Numerical results and industrial applications

paper_content:

A (general) circle packing is an optimized arrangement of N arbitrary sized circles inside a container (e.g., a rectangle or a circle) such that no two circles overlap. In this paper, we present several circle packing problems, review their industrial applications, and some exact and heuristic strategies for their solution. We also present illustrative numerical results using 'generic' global optimization software packages. Our work highlights the relevance of global optimization in solving circle packing problems, and points towards the necessary advancements in both theory and numerical practice.
---

Title: A Literature Review on Circle and Sphere Packing Problems: Models and Methodologies

Section 1: Introduction
Description 1: Introduce cutting and packing problems, their applications, and the specific focus on circular objects in two and three dimensions.

Section 2: Polygonal Region Ω
Description 2: Discuss problems related to packing circles within polygonal regions, differentiating between two-dimensional and three-dimensional cases.

Section 3: Two-Dimensional Case
Description 3: Explore methods and models for packing circles in two-dimensional shapes such as squares, rectangles, and various polygons.

Section 4: Packing Circles into a Square
Description 4: Review methods and results for packing identical circles within a unit square to maximize minimal distances or other objectives.

Section 5: Packing Circles into a Rectangle
Description 5: Examine problems and solutions related to packing circles into a fixed-size or minimal area rectangle, with variations for identical and nonidentical circles.

Section 6: Packing Circles in a Compact Polygon Set
Description 6: Discuss the problem of covering a polygonal region with identical circles of minimal radius and methods used.

Section 7: Three-Dimensional Case
Description 7: Cover problems and methodologies for packing spheres in three-dimensional regions such as cubes, parallelepipeds, cylinders, and polytopes.

Section 8: Circular Region Ω
Description 8: Focus on circle packing problems (CPP) in circular regions, including applications, challenges, and distinctions between packing identical and nonidentical circles.

Section 9: Packing Identical Circles
Description 9: Summarize approaches for packing identical circles into a unit circle, including specific models and heuristic methods.

Section 10: Packing Nonidentical Circles
Description 10: Explore the methodologies for packing nonidentical circles into the smallest containing circle, emphasizing combinatorial and continuous optimization challenges.

Section 11: Conclusion
Description 11: Summarize the findings from the literature review and discuss the advancements in the field and potential future research directions.