A LINEAR-TIME ALGORITHM FOR COVERING SIMPLE POLYGONS WITH SIMILAR RECTANGLES
- 1 March 1996
- journal article
- Published by World Scientific Pub Co Pte Ltd in International Journal of Computational Geometry & Applications
- Vol. 6 (1) , 79-102
- https://doi.org/10.1142/s021819599600006x
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.Keywords
This publication has 0 references indexed in Scilit: