IMI Interdisciplinary Mathematics InstituteCollege of Arts and Sciences

A rectangle tacking problem

  • Sept. 28, 2018
  • 2:30 p.m.
  • LeConte 317R

Abstract

Rectangle packing problem can be described as a one-round game between Alice and Bob. First, Alice chooses a finite point set in the unit square in the plane, including the origin. Then Bob chooses an axis-aligned rectangle for each point such that each point is the lower-left corner of the rectangle, and rectangles are interior-disjoint with each other. The problem is, can Bob always cover a constant total area of rectangles? This dissertation expands on the recent proof of Dumitrescu and Toth that Bob can cover at least 9.121% of the unit square for any point set. To verify this result, two algorithms, GreedyPacking and TilePacking, are introduced first. By comparing the performance of two algorithms, it comes to a conclusion that GreedyPacking always covers an area at least as large as the area covered by TilePacking. Therefore, only TilePacking is analysed later. Then, the geometric interpretation of TilePacking is analysed. After that, it’ shows that TilePacking can guarantee Bob to cover at least 9.121% of the unit square. Since GreedyPacking performs better than TilePacking, this result holds for GreedyPacking as well.

© Interdisciplinary Mathematics Institute | The University of South Carolina Board of Trustees | Webmaster
USC