Robotics and Intelligent Machines
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+ε, where n is a positive integer and ε 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.
American Mathematical Society: Third Award of $500
Third Award of $1,000