Performance Guarantees on a Sweep-Line Heuristic for Covering Rectilinear Polygons with Rectangles

DOI10.1137/0402027zbMath0673.05018MaRDI QIDQ3826568

D. S. Franzblau

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

zbMATH Keywords

covering; approximation algorithm; rectilinear polygon; orthogonal polygon

Mathematics Subject Classification ID

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

Complexities of efficient solutions of rectilinear polygon cover problems, Lower bounds for approximate polygon decomposition and minimum gap