Polygon covering
In geometry, a covering of a polygon is a set of primitive units (e.g. squares) whose union equals the 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. An example polygon covering problem is: given a rectilinear polygon, find a smallest set of squares whose union equals the polygon.
In some scenarios, it is not required to cover the entire polygon but only its edges (this is called polygon edge covering) or its vertices (this is called polygon vertex covering).
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 polygon 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.
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
[edit]A rectilinear polygon can always be covered with a finite number of vertices of the polygon.[1] The algorithm uses a local optimization approach: it builds the covering by iteratively selecting maximal squares that are essential to the cover (i.e., contain uncovered points not covered by other maximal squares) and then deleting from the polygon the points that become unnecessary (i.e., unneeded to support future squares). Here is a simplified pseudo-code of the algorithm:
- While the polygon P is not empty:
- Select a continuator square s in P.
- If the balcony of s is not yet covered, then add s to the covering.
- Remove the balcony of s from P.
- If what remains of s is a one-knob continuator, then remove from P a certain rectangle adjacent to the knob, taking care to leave a sufficient security distance for future squares.
For polygons which may contain holes, finding a minimum such covering is NP-hard.[2] This sharp difference between hole-free and general polygons can be intuitively explained based on the following analogy between maximal squares in a rectilinear polygon and nodes in an undirected graph:[1]
- Some maximal squares have a continuous intersection with the boundary of the polygon; when they are removed, the remaining polygon remains connected. Such squares are called "continuators" and are analogous to leaf nodes – nodes with a single edge – that can be removed without disconnecting the graph.
- Other maximal squares are "separators": when they are removed, the polygon splits into two disconnected polygons. They are analogous to nodes with two or more edges that, when removed, leave a disconnected remainder.
In a hole-free rectilinear polygon, all maximal squares are either continuators or separators; thus, such a polygon is analogous to a tree graph. A general polygon is analogous to a general graph. Just like the vertex cover problem is polynomial for tree graphs but NP-hard for general graphs, the square covering problem is linear for hole-free polygons but NP-hard for general polygons.
It is possible to use the linear algorithm to get a 2-approximation; i.e., a covering with at most 2 opt squares, where opt is the number of squares in a minimum covering:[3]
- For each hole, find a square s connecting the hole to the external boundary.
- Cut s from the polygon, then glue back two overlapping copies of s (see figure). The resulting polygon is not planar, but it still 2-dimensional, and now it has no holes.
- Now use the original algorithm to find a minimum covering.
The number of squares in the resulting covering is at most opt + holes, where holes is the number of holes. It is possible to prove that opt ≥ holes. Hence the number of squares in the covering is at most 2 opt.
Covering a rectilinear polygon with rectangles
[edit]For general rectilinear polygons, the problem of finding a minimum rectangle covering is NP-hard, even when the target polygon is hole-free.[4] Several partial solutions have been suggested to this problem:
- 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.[5]
- Even when the target polygon is only half-orthogonally convex (i.e. only in the y direction), a minimum covering by rectangles can be found in time O(n2), where n is the number of vertices of the polygon.[6]
- An approximation algorithm which gives good empirical results on real-life data is presented by.[7]
- For rectilinear polygons which may contain holes, there is an O(√log n) factor approximation algorithm.[8]
Covering a rectilinear polygon with orthogonally convex polygons
[edit]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.[9]
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).[10]
Covering a rectilinear polygon with star polygons
[edit]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 problem of covering a polygon with star polygons is a variant of the art gallery problem.
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.[11]
Covering a polygon without acute angles with squares or rectangles
[edit]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.[12]
Covering a polygon with rectangles of a finite family
[edit]In some cases, a polygon has to be covered not with arbitrary rectangles but with rectangles from a finite family.[13]
Covering a polygon with triangles
[edit]Finding the smallest set of triangles covering a given polygon is NP-hard. It is also hard to approximate - every polynomial-time algorithm might find a covering with size (1 + 1/19151) times the minimal covering.[14]
If the polygon is in general position (i.e. no two edges are collinear), then every triangle can cover at most 3 polygon edges. Hence every polygon triangulation is a 3-approximation.
If the covering is restricted to triangles whose vertices are vertices of the polygon (i.e. Steiner points are not allowed), then the problem is NP-complete.
If Steiner points are not allowed and the polygon is in general position (i.e. no two edges are collinear), then every minimal covering without Steiner points is also a minimal partitioning of the polygon to triangles (i.e., the triangles in the minimal covering to not overlap).[14] Hence, the minimum covering problem is identical to the polygon triangulation problem, which can be solved in time O(nlog n). Note that if we drop the general position assumption, there are polygons in which the triangles in the optimal covering overlap. Think of the Star of David for example.
The problem of covering only the boundary of a polygon with triangles is NP-complete, but there is an efficient 2-approximation.[14]
Covering a polygon with convex polygons
[edit]Covering a polygon (which may contain holes) with convex polygons is NP-hard.[15] It has also been shown to be -complete. [16] There is an O(log n) approximation algorithm.[17]
Covering a polygon with convex polygons is NP-hard even when the target polygon is hole-free.[4] It is also APX-hard,[17] but there is a 6-approximation algorithm for the hole-free case.[18] The problem is NP-complete when the covering must not introduce new vertices (i.e. Steiner points are not allowed).[14]
Covering a polygon with star polygons
[edit]Covering a simple polygon with star polygons is -complete, as is the version where a point in the kernel of each star must be contained in an edge of the polygon.[19]
Covering a set of points with identical squares
[edit]Given a set S of points in the plane, and a set of identical squares, the goal is to find the smallest number of squares that can cover all points in S.
Suppose that, for each point p in S, we put a square centered at p. Let GS be the intersection graph of these squares. Note that two points in S can be covered by a single square, if and only if the two squares centered at them overlap. Therefore, a square-covering of the points in S is equivalent to a clique cover of GS. Finding a smallest square-covering of S is NP-hard; the proof is by reduction from 3SAT.[20]
Other combinations
[edit]Covering a polygon (which may contain holes) with spiral polygons is NP-hard.[15]
Covering a polygon with pseudotriangles has also been studied.
Additional information can be found in.[21]
See also
[edit]References
[edit]- ^ Jump up to: a b Bar-Yehuda, R.; Ben-Hanoch, E. (1996). "A Linear-Time Algorithm for Covering Simple Polygons with Similar Rectangles". International Journal of Computational Geometry & Applications. 06: 79–102. doi:10.1142/S021819599600006X.
- ^ 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.
- ^ Prof. Reuven Bar-Yehuda in personal communication
- ^ Jump up to: a b Culberson, J. C.; Reckhow, R. A. (1988). "Covering polygons is hard". [Proceedings 1988] 29th Annual Symposium on Foundations of Computer Science. p. 601. doi:10.1109/sfcs.1988.21976. ISBN 978-0-8186-0877-3. S2CID 34508387..
- ^ Chaiken, S.; Kleitman, D. J.; Saks, M.; Shearer, J. (1981). "Covering Regions by Rectangles". SIAM Journal on Algebraic and Discrete Methods. 2 (4): 394. doi:10.1137/0602042.
- ^ Franzblau, D. S.; Kleitman, D. J. (1984). "An algorithm for constructing regions with rectangles". Proceedings of the sixteenth annual ACM symposium on Theory of computing - STOC '84. p. 167. doi:10.1145/800057.808678. ISBN 978-0897911337.
- ^ Heinrich-Litan, L.; Lübbecke, M. E. (2007). "Rectangle covers revisited computationally". Journal of Experimental Algorithmics. 11: 2.6. CiteSeerX 10.1.1.69.4576. doi:10.1145/1187436.1216583. S2CID 619557.
- ^ Kumar, V. S. A.; Ramesh, H. (2003). "Covering Rectilinear Polygons with Axis-Parallel Rectangles". SIAM Journal on Computing. 32 (6): 1509. CiteSeerX 10.1.1.20.2664. doi:10.1137/s0097539799358835.
- ^ Keil, J. M. (1986). "Minimally covering a horizontally convex orthogonal polygon". Proceedings of the second annual symposium on Computational geometry - SCG '86. pp. 43–51. doi:10.1145/10515.10520. ISBN 978-0897911948.
- ^ Culberson, J.; Reckhow, R. A. (1989). "Orthogonally convex coverings of orthogonal polygons without holes". Journal of Computer and System Sciences. 39 (2): 166. doi:10.1016/0022-0000(89)90043-3.
- ^ Motwani, R.; Raghunathan, A.; Saran, H. (1990). "Covering orthogonal polygons with star polygons: The perfect graph approach". Journal of Computer and System Sciences. 40: 19–48. doi:10.1016/0022-0000(90)90017-f.
- ^ Levcopoulos, C.; Gudmundsson, J. (1997). "Approximation algorithms for covering polygons with squares and similar problems". Randomization and Approximation Techniques in Computer Science. Lecture Notes in Computer Science. Vol. 1269. p. 27. CiteSeerX 10.1.1.22.9094. doi:10.1007/3-540-63248-4_3. ISBN 978-3-540-63248-1., Grazyna Zwozniak, 1998
- ^ Stoyan, Y. G.; Romanova, T.; Scheithauer, G.; Krivulya, A. (2009). "Covering a polygonal region by rectangles". Computational Optimization and Applications. 48 (3): 675. doi:10.1007/s10589-009-9258-1. S2CID 15599243.
- ^ Jump up to: a b c d Christ, T. (2011). "Beyond Triangulation: Covering Polygons with Triangles". Algorithms and Data Structures. Lecture Notes in Computer Science. Vol. 6844. pp. 231–242. doi:10.1007/978-3-642-22300-6_20. ISBN 978-3-642-22299-3.
- ^ Jump up to: a b O'Rourke, J.; Supowit, K. (1983). "Some NP-hard polygon decomposition problems". IEEE Transactions on Information Theory. 29 (2): 181. doi:10.1109/tit.1983.1056648.
- ^ Abrahamsen, Mikkel. "Covering Polygons is Even Harder" (PDF). IEEE-FOCS.
- ^ Jump up to: a b Eidenbenz, S.; Widmayer, P. (2001). "An Approximation Algorithm for Minimum Convex Cover with Logarithmic Performance Guarantee". Algorithms — ESA 2001. Lecture Notes in Computer Science. Vol. 2161. p. 333. doi:10.1007/3-540-44676-1_28. ISBN 978-3-540-42493-2.
- ^ "Program- FOCS 2023". FOCS 2023. IEEE.
- ^ Abrahamsen, Mikkel; Adamaszek, Anna; Miltzow, Tillmann (2017), The Art Gallery Problem is -complete, arXiv:1704.06969, Bibcode:2017arXiv170406969A
- ^ Fowler, Robert J.; Paterson, Michael S.; Tanimoto, Steven L. (1981-06-13). "Optimal packing and covering in the plane are NP-complete". Information Processing Letters. 12 (3): 133–137. doi:10.1016/0020-0190(81)90111-3. ISSN 0020-0190.
- ^ Keil, J. M. (2000). "Polygon Decomposition". Handbook of Computational Geometry. pp. 491–518. doi:10.1016/B978-044482537-7/50012-7. ISBN 9780444825377.