@Article{BarBen96, author = "R. Bar-Yehuda and E. Ben-Hanoch", title = "A Linear Time Algorithm for Covering Simple Polygons With Similar Rectangles", journal = "Int. J. of Computational Geometry \& Appl.", volume = "6", number = "1", pages = "79--102", year = "1996", abstract = "We study the problem of covering a simple orthogonal polygon with a minimum number of (possibly overlapping) squares, all internal to the polygon. The problem has applications in VLSI mask generation, incremental update of raster displays, and image compression. We give a linear time algorithm for covering a simple polygon, specified by its vertices, with squares. Covering with similar rectangles (having a given x/y ratio) is an equivalent problem.", }