Covering Rectilinear Polygons with Axis-Parallel Rectangles

DOI10.1137/S0097539799358835MaRDI QIDQ4441891zbMATH OpenOpenAlexFDO

Authors V. S. Anil Kumar, H. Ramesh

Publication date 8 January 2004

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0097539799358835

zbMATH Keywords

approximation algorithmscovering polygons

Mathematics Subject Classification ID

Packing and covering in (2) dimensions (aspects of discrete geometry) (52C15) Approximation algorithms (68W25) Analysis of algorithms (68W40)

Recommendations

• Covering rectilinear polygons with axis-parallel rectangles
• A linear-time heuristic for minimum rectangular coverings (Extended abstract)
• Close approximations of minimum rectangular coverings
• COVERING CONVEX RECTILINEAR POLYGONS IN LINEAR TIME
• Performance Guarantees on a Sweep-Line Heuristic for Covering Rectilinear Polygons with Rectangles

Cited in

(17)

• On point covers of parallel rectangles
• Rectangulating rectilinear polygons in parallel
• Orientational variable-length strip covering problem: a branch-and-price-based algorithm
• Drawing borders efficiently
• Covering rectilinear polygons with axis-parallel rectangles
• Covering a set of points by two axis-parallel boxes
• The Boolean Basis Problem and How to Cover Some Polygons by Rectangles
• scientific article; zbMATH DE number 5291457 (Why is no real title available?)
• scientific article; zbMATH DE number 29609 (Why is no real title available?)
• Covering and packing of rectilinear subdivision
• Computing coverage kernels under restricted settings
• Rectangulating rectilinear polygons in parallel
• A hybrid heuristic for the rectilinear picture compression problem
• Covering rectilinear polygons with area-weighted rectangles
• Box covers and domain orderings for beyond worst-case join processing
• Covering simple orthogonal polygons with rectangles
• Covering a set of points in a plane using two parallel rectangles

This page was built for publication: Covering Rectilinear Polygons with Axis-Parallel Rectangles

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