Covering Squares of Side Length n+e with Unit Squares

Overview

The topic of this project is influenced by a classical combinatorial geometry open problem, which recently sparked new interest - square covering. It is one of the fields, known to have applications in image processing and the attempts to increase yield in VLSI chip manufacture. Our main question is to find the smallest number of unit squares that can cover a square of side length n+e, where n is a positive integer and e is a sufficiently small positive number. The problem is solved only for n=1, in which case the desired smallest number is known to be 3. For all other values of n the problem is open. Soifer's construction (2006) is known to give optimal upper bounds for this number, both asymptotically and for particular values of n. In the current project we introduce a new construction. We study it according to the argument k, introduced by Soifer, and we obtain new, generalized results. We obtain improvements on the bound of Soifer for every finite value of n, while the asymptotics remain the same. We have paid special attention to the cases k=0 and k=1, where the bounds are at their closest, and studied the results analytically. We have successfully defined the conditions which determine the outcome for a particular value of n in these two cases.

Awards (2)

• Third Award of $1,000 $1,000
• American Mathematical Society: Third Award of $500 $500

Competition history

• ISEF 2014 Robotics and Intelligent Machines · Entry MA035

Resources

• ISEF abstract page ↗

Related projects

Closest projects by meaning, across every fair and year in the corpus.