An algorithm for constructing regions with rectangles

1 January 1984

proceedings article
Published by Association for Computing Machinery (ACM)

p. 167-174
https://doi.org/10.1145/800057.808678

Abstract

We provide an algorithm which solves the following problem: given a polygon with edges parallel to the x and y axes, which is convex in the y direction, find a minimum size collection of rectangles, which cover the polygon and are contained within it. The algorithm is quadratic in the number of vertices of the polygon. Our method also yields a new proof of a recent duality theorem equating minimum size rectangle covers to maximum size sets of independent points in the polygon.

Keywords

MINIMUM SIZE RECTANGLE
MINIMUM GENERATING SET
INDEPENDENT POINT
MINIMUM SIZE COLLECTION
FOLLOWING PROBLEM
Y DIRECTION
NEW PROOF
EDGES PARALLEL
Y AXIS
RECENT DUALITY THEOREM
MAXIMUM SIZE SET
COMPACTNESS
ALGORITHM

This publication has 0 references indexed in Scilit: