Performance Guarantees on a Sweep-Line Heuristic for Covering Rectilinear Polygons with Rectangles
From MaRDI portal
Publication:3826568
DOI10.1137/0402027zbMath0673.05018MaRDI QIDQ3826568
Publication date: 1989
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0402027
68Q25: Analysis of algorithms and problem complexity
52C17: Packing and covering in (n) dimensions (aspects of discrete geometry)
05B40: Combinatorial aspects of packing and covering
05B50: Polyominoes
68R99: Discrete mathematics in relation to computer science
Related Items
A linear-time heuristic for minimum rectangular coverings (Extended abstract), A hybrid heuristic for the rectilinear picture compression problem, Complexities of efficient solutions of rectilinear polygon cover problems, Lower bounds for approximate polygon decomposition and minimum gap