| Covering Rectilinear Polygons with Axis-Parallel Rectangles (2003) | |||||||||
Abstract | |||||||||
| SIAM COMPUT Vol pp Society for Industrial and Applied Mathematics COVERING RECTILINEAR POLYGONS WITH AXIS PARALLEL RECTANGLES ANIL KUMAR AND RAMESH Abstract give log factor approximation algorithm for covering rectilinear polygon with holes using axis parallel rectangles This the first polynomial time approximation algorithm for this problem with log approximation factor Key words approximation algorithms covering polygons AMS subject classifications W DOI Introduction consider the problem covering rectilinear polygons with axis parallel rectangles Given rectilinear polygon with complexity complexity refers the minimum the number vertical edges and the number horizontal edges the polygon this problem requires determining the minimum number axis parallel rectangles whose union covers The polygon may have holes Applications Cheng Iyengar and Kashyap showed that this problem has applications image compression They claim that representing image using rectangle covering its white pixels gives compression superior that achieved quadtrees also has applications printing integrated circuits Hardness Much effort has gone into determining the computational complexity this problem spite this the exact complexity this problem has remained open for many years and continues Masek showed that this problem complete Later Culberson and Reckhow used clever reduction from SAT show that this the case even when has holes The next natural question whether the number rectangles needed cover can comp | |||||||||
Publication details | |||||||||
| |||||||||