An algorithm for covering polygons with rectangles

DOI10.1016/S0019-9958(84)80012-1MaRDI QIDQ3719852zbMATH OpenOpenAlexFDO

Authors D. S. Franzblau, Daniel J. Kleitman

Publication date 1984

Published in Information and Control (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0019-9958(84)80012-1

zbMATH Keywords

algorithmcomputational geometryminimum number of rectangles, with overlapping allowedpolyominorectilinear polygon

Mathematics Subject Classification ID

Combinatorial aspects of packing and covering (05B40) Discrete mathematics in relation to computer science (68R99)

Recommendations

• scientific article; zbMATH DE number 3893101
• COVERING CONVEX RECTILINEAR POLYGONS IN LINEAR TIME
• Performance Guarantees on a Sweep-Line Heuristic for Covering Rectilinear Polygons with Rectangles
• scientific article; zbMATH DE number 3872705
• Close approximations of minimum rectangular coverings

Cited in

(28)

• Covering simply connected regions by rectangles
• A weighted min-max relation for intervals
• Complexity of minimum biclique cover and minimum biclique decomposition for bipartite domino-free graphs
• Finding minimum generators of path systems
• Pushdown-reduce: An algorithm for connectivity augmentation and poset covering problems
• An algorithm for polygon placement using a bottom-left strategy
• Independent sets and hitting sets of bicolored rectangular families
• Optimized location of light sources to cover a rectangular region
• A dual of the rectangle-segmentation problem for binary matrices
• CONY, an algorithm for a nonoverlapping covering of a nonconvex multipy connected polygon by simply connected sets.
• Jump number of two-directional orthogonal ray graphs
• Building a consensus: a rectangle covering problem
• The Boolean Basis Problem and How to Cover Some Polygons by Rectangles
• scientific article; zbMATH DE number 5291457 (Why is no real title available?)
• Minimum vertex cover in rectangle graphs
• Performance Guarantees on a Sweep-Line Heuristic for Covering Rectilinear Polygons with Rectangles
• scientific article; zbMATH DE number 17532 (Why is no real title available?)
• COVERING CONVEX RECTILINEAR POLYGONS IN LINEAR TIME
• scientific article; zbMATH DE number 736298 (Why is no real title available?)
• Covering Orthogonal Polygons with Non-Piercing Rectangles
• Algorithms for Rectangular Covering Problems
• Minimum vertex cover in rectangle graphs
• Algorithms for deciding the containment of polygons
• Complexities of efficient solutions of rectilinear polygon cover problems
• Box covers and domain orderings for beyond worst-case join processing
• Packing resizable items with application to video delivery over wireless networks
• A minimax theorem on intervals
• An algorithm for the difference between set covers

This page was built for publication: An algorithm for covering polygons with rectangles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3719852)