Javascript verkar inte påslaget? - Vissa delar av Lunds universitets webbplats fungerar inte optimalt utan javascript, kontrollera din webbläsares inställningar.
Du är här

Close Approximations of Minimum Rectangular Coverings

Publiceringsår: 1999
Språk: Engelska
Sidor: 437-452
Publikation/Tidskrift/Serie: Journal of Combinatorial Optimization
Volym: 3
Nummer: 4
Dokumenttyp: Artikel i tidskrift
Förlag: Kluwer


We consider the problem of covering arbitrary polygons with rectangles. The rectangles must lie entirely within the polygon. (This requires that the interior angles of the polygon are all greater than or equal to 90 degrees.) We want to cover the polygon with as few rectangles as possible. This problem has an application in fabricating masks for integrated circuits.

In this paper we will describe the first polynomial algorithm, guaranteeing an O(log n) approximation factor, provided that the n vertices of the input polygon are given as polynomially bounded integer coordinates. By the same technique we also obtain the first algorithm producing a covering which is within a constant factor of the optimal in exponential time (compared to the doubly-exponential known before).


  • Computer Science
  • computational geometry
  • covering polygons
  • approximation algorithms


  • ISSN: 1382-6905

Box 117, 221 00 LUND
Telefon 046-222 00 00 (växel)
Telefax 046-222 47 20
lu [at] lu [dot] se

Fakturaadress: Box 188, 221 00 LUND
Organisationsnummer: 202100-3211
Om webbplatsen