Polygon covering: Difference between revisions

Content deleted Content added

Inline

Revision as of 14:59, 13 June 2014

A polygon covering is a set of small units (e.g. squares) whose union equals a larger polygon. A polygon covering problem is a problem of finding a covering with a smallest number of units for a given polygon. This is an important class of problems in computational geometry. There are many different polygon covering problems, depending on the type of polygon being covered and on the types of units allowed in the covering. An example polygon covering problem is: given a rectilinear polygon, find a smallest set of squares whose union equals the polygon.

In a covering problem, the units in the covering are allowed to overlap, as long as their union is exactly equal to the target polygon. This is in contrast to a packing problem, in which the units must be disjoint and their union may be smaller than the target polygon, and to a partition problem, in which the units must be disjoint and their union must be equal to the target polygon.

A polygon covering problem is a special case of the set cover problem. In general, the problem of finding a smallest set covering is NP-complete, but for special classes of polygons, a smallest polygon covering can be found in polynomial time.

Basic concepts

A unit u contained in a polygon P is called maximal if it is not contained in any other unit in P. When looking for a polygon covering, it is sufficient to consider maximal units, since every unit which is not maximal can be replaced with a maximal unit containing it without affecting the size of the covering.

A covering of a polygon P is a collection of maximal units, possibly overlapping, whose union equals P.

A minimal covering is a covering that does not contain any other covering (i.e. it is a local minimum).

A minimum covering is a covering with a smallest number of units (i.e. a global minimum). Every minimum covering is minimal, but not vice versa.

Covering a rectilinear polygon with squares

A rectilinear polygon can always be covered with a finite number of squares.

For polygons which may contain holes, finding a minimum such covering is NP-hard.^[1]

For hole-free polygons, a minimum covering by squares can be found in time O(n), where n is the number of vertices of the polygon.^[2]

Covering a rectilinear polygon with rectangles

For general rectilinear polygons, the problem of finding a minimum rectangle covering is NP-hard, even when the target polygon is hole-free.^[3] Several partial solutions have been suggested to this problem:

1. In orthogonally convex polygons, the number of rectangles in a minimum covering is equal to the number of blocks in an anti rectangle, and this fact can be used to build a polynomial time algorithm for finding a minimum covering by rectangles. ^[4]

2. Even when the target polygon is only half-orthogonally convex (i.e. only in the y direction), a minimum covering by rectangle can be found in time O(n²), where n is the number of vertices of the polygon.^[5]

3. An approximation algorithm which gives good empirical results on real-life data is presented by ^[6].

4. For rectilinear polygons which may contain holes, there is an O(√ log n) factor approximation algorithm.^[7]

Covering a rectilinear polygon with orthogonally convex polygons

For a rectilinear polygon which is half-orthogonally convex (i.e. only in the x direction), a minimum covering by orthogonally convex polygons can be found in time O(n^2), where n is the number of vertices of the polygon. The same is true for a covering by rectilinear star polygons.^[8]

The number of orthogonally-convex components in a minimum covering can, in some cases, be found without finding the covering itself, in time O(n).^[9]

Covering a rectilinear polygon with star polygons

A rectilinear star polygon is a polygon P containing a point p, such that for every point q in P, there is an orthogonally convex polygon containing p and q.

The visibility graph for the problem of minimally covering hole-free rectilinear polygons with star polygons is a perfect graph. This perfectness property implies a polynomial algorithm for finding a minimum covering of any rectilinear polygon with rectilinear star polygons.^[10]

Covering a polygon without acute angles with squares or rectangles

The most general class of polygons for which coverings by squares or rectangles can be found is the class of polygons without acute interior angles. This is because an acute angle cannot be covered by a finite number of rectangles. This problem is NP-hard, but several approximation algorithms exist.^[11]

Covering general polygons

In many cases, finding a polygon covering is NP-hard. In particular:

The problems of covering a polygon (which may contain holes) with convex polygons, star polygons or spirals are all NP-hard.^[12]

Covering a polygon with convex polygons is NP-hard even when the target polygon is hole-free.^[3]

Covering a polygon with star polygons is also NP-hard even when the target polygon is hole-free.^[13]

References

^ Aupperle, L.J.; Conn, H.E.; Keil, J.M.; O'Rourke, Joseph (1988). "Covering orthogonal polygons with squares". Proc. 26th Allerton Conf. Commun. Control Comput.: 97–106.
^ Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1142/S021819599600006X, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with |doi=10.1142/S021819599600006X instead.
^ ^a ^b Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1109/sfcs.1988.21976, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with |doi=10.1109/sfcs.1988.21976 instead..
^ Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1137/0602042, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with |doi=10.1137/0602042 instead.
^ Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1145/800057.808678, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with |doi=10.1145/800057.808678 instead.
^ Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1145/1187436.1216583, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with |doi=10.1145/1187436.1216583 instead.
^ Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1137/s0097539799358835, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with |doi=10.1137/s0097539799358835 instead.
^ Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1145/10515.10520, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with |doi=10.1145/10515.10520 instead.
^ Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1016/0022-0000(89)90043-3, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with |doi=10.1016/0022-0000(89)90043-3 instead.
^ Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1016/0022-0000(90)90017-f, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with |doi=10.1016/0022-0000(90)90017-f instead.
^ Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1007/3-540-63248-4_3, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with |doi=10.1007/3-540-63248-4_3 instead., Grazyna Zwozniak, 1998
^ Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1109/tit.1983.1056648, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with |doi=10.1109/tit.1983.1056648 instead.
^ Aggarwal, Alok (1984). The art gallery theorem: its variations, applications and algorithmic aspects. The Johns Hopkins University: Department of Electrical Engineering and Computer Science.

@@ Line 42: / Line 42: @@
 The visibility graph for the problem of minimally covering hole-free [[rectilinear polygon]]s with star polygons is a [[perfect graph]]. This perfectness property implies a polynomial algorithm for finding a minimum covering of any rectilinear polygon with rectilinear star polygons.<ref>{{Cite doi|10.1016/0022-0000(90)90017-f}}</ref>
-== Covering a polygon without acute angles with rectangles ==
+== Covering a polygon without acute angles with squares or rectangles ==
-The most general class of polygons for which rectangle coverings can be found is the class of polygons without acute interior angles. This is because an acute angle cannot be covered by a finite number of rectangles. This problem is NP-hard, but several approximation algorithms exist.<ref>Christos Levcopoulos and Joachim Gudmundsson, 1997; Grazyna Zwozniak, 1998</ref>
+The most general class of polygons for which coverings by squares or rectangles can be found is the class of polygons without acute interior angles. This is because an acute angle cannot be covered by a finite number of rectangles. This problem is NP-hard, but several approximation algorithms exist.<ref>{{Cite doi|10.1007/3-540-63248-4_3}}, Grazyna Zwozniak, 1998</ref>
 == Covering general polygons ==