Name
Title | ||
|---|---|---|
An algorithm for constructing regions with rectangles: Independence and minimum generating sets for collections of intervals |
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. |
Year | DOI | Venue |
|---|---|---|
1984 | 10.1145/800057.808678 | STOC |
Keywords | Field | DocType |
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 | Discrete mathematics,Combinatorics,Polygon,Rectilinear polygon,Polygon covering,Algorithm,Pick's theorem,Simple polygon,Affine-regular polygon,Star-shaped polygon,Equiangular polygon,Mathematics | Conference |
ISBN | Citations | PageRank |
0-89791-133-4 | 20 | 7.15 |
References | Authors | |
0 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Deborah S. Franzblau | 1 | 25 | 9.24 |
| Daniel J. Kleitman | 2 | 854 | 277.98 |