  


Rigorous packing of unit squares into a circle
Tiago Montanher(tiago.de.morais.montanherunivie.ac.at) Abstract: Let $r_{n}$ be the radius of the smallest circle into which one can pack $n$ nonoverlapping unit squares that are free to rotate. For $n = 1, 2$, $r_{1} = \frac{\sqrt{2}}{2}$ and $r_{2} = \frac{\sqrt{5}}{2}$ are proved to be optimal. For $n \geq 3$ only guesses of $r_{n}$ are known. This paper introduces a computerassisted method to find rigorous enclosures for $r_{n}$ and the corresponding optimal arrangements. Given an upper bound $\ol r_{n} > 0$ for $r_{n}$, we formulate the containment and the nonoverlapping conditions as a constraint satisfaction problem (CSP) and ask for every arrangement satisfying $r_{n} \leq \ol r_{n}$. We solve the problem using an interval branchandbound procedure implemented in the rigorous solver \GL {} to ensure the mathematical certainty of our statements. General purpose interval methods cannot solve the CSP due to symmetries in the search domain. To overcome this difficulty, we split the problem into a set of subproblems by adding tiling constraints specially designed for the packing of unit squares. Our procedure also iterates on the number of squares to discard simple subproblems and avoid the exponential growth of hard ones. As an application, we find a rigorous enclosure for the optimal arrangement of $n = 3$. In this case, the proof requires the solution of $6$, $43$ and $12$ subproblems with $1$, $2$ and $3$ unit squares respectively. Keywords: Square packing into a circle; Interval branchandbound; Tiling constraints; Computerassisted proof Category 1: Global Optimization Citation: Submitted Download: [PDF] Entry Submitted: 04/03/2018 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  