192:
501:(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). Hence, the minimum covering problem is identical to the polygon triangulation problem, which can be solved in time O(
454:
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.
206:
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
125:
can always be covered with a finite number of vertices of the polygon. 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
471:
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.
210:
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
202:. 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:
302:
For general rectilinear polygons, the problem of finding a minimum rectangle covering is NP-hard, even when the target polygon is hole-free. Several partial solutions have been suggested to this problem:
1326:
606:
547:
84:. 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.
223:
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.
126:
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:
564:, but there is a 6-approximation algorithm for the hole-free case. The problem is NP-complete when the covering must not introduce new vertices (i.e.
43:. There are many different polygon covering problems, depending on the type of polygon being covered. An example polygon covering problem is: given a
446:. This perfectness property implies a polynomial algorithm for finding a minimum covering of any rectilinear polygon with rectilinear star polygons.
509:). Note that if we drop the general position assumption, there are polygons in which the triangles in the optimal covering overlap. Think of the
487:
384:
The number of orthogonally-convex components in a minimum covering can, in some cases, be found without finding the covering itself, in time O(
1267:
1179:
1103:
810:
65:, 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
656:
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
622:
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
1226:
994:
879:
215:
In a hole-free rectilinear polygon, all maximal squares are either continuators or separators; thus, such a polygon is analogous to a
1414:
1250:
Eidenbenz, S.; Widmayer, P. (2001). "An
Approximation Algorithm for Minimum Convex Cover with Logarithmic Performance Guarantee".
39:
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
516:
The problem of covering only the boundary of a polygon with triangles is NP-complete, but there is an efficient 2-approximation.
1436:
583:
113:
is a covering with a smallest number of units (i.e. a global minimum). Every minimum covering is minimal, but not vice versa.
1076:
Levcopoulos, C.; Gudmundsson, J. (1997). "Approximation algorithms for covering polygons with squares and similar problems".
1451:
739:
Bar-Yehuda, R.; Ben-Hanoch, E. (1996). "A Linear-Time
Algorithm for Covering Simple Polygons with Similar Rectangles".
1446:
463:
In some cases, a polygon has to be covered not with arbitrary rectangles but with rectangles from a finite family.
185:
a certain rectangle adjacent to the knob, taking care to leave a sufficient security distance for future squares.
1120:
Stoyan, Y. G.; Romanova, T.; Scheithauer, G.; Krivulya, A. (2009). "Covering a polygonal region by rectangles".
191:
766:
Aupperle, L.J.; Conn, H.E.; Keil, J.M.; O'Rourke, Joseph (1988). "Covering orthogonal polygons with squares".
316:, and this fact can be used to build a polynomial time algorithm for finding a minimum covering by rectangles.
524:
Covering a polygon (which may contain holes) with convex polygons is NP-hard. It has also been shown to be
1306:
1081:
949:
904:
610:, as is the version where a point in the kernel of each star must be contained in an edge of the polygon.
586:
527:
40:
480:
256:(see figure). The resulting polygon is not planar, but it still 2-dimensional, and now it has no holes.
69:, in which the units must be disjoint and their union may be smaller than the target polygon, and to a
479:(i.e. no two edges are collinear), then every triangle can cover at most 3 polygon edges. Hence every
1341:
565:
50:
In some scenarios, it is not required to cover the entire polygon but only its edges (this is called
1283:
313:
1086:
954:
940:
Kumar, V. S. A.; Ramesh, H. (2003). "Covering
Rectilinear Polygons with Axis-Parallel Rectangles".
909:
862:
Franzblau, D. S.; Kleitman, D. J. (1984). "An algorithm for constructing regions with rectangles".
711:
577:
439:
432:
417:
366:
358:
309:
226:
It is possible to use the linear algorithm to get a 2-approximation; i.e., a covering with at most
152:
138:
122:
44:
1331:
1137:
922:
816:
649:
32:
334:
An approximation algorithm which gives good empirical results on real-life data is presented by.
312:
polygons, the number of rectangles in a minimum covering is equal to the number of blocks in an
1441:
1410:
1379:
1263:
1175:
1099:
990:
875:
835:
Chaiken, S.; Kleitman, D. J.; Saks, M.; Shearer, J. (1981). "Covering
Regions by Rectangles".
806:
706:
81:
70:
62:
1402:
1371:
1255:
1207:
1167:
1129:
1091:
1056:
1023:
982:
959:
914:
867:
844:
798:
748:
498:
486:
If the covering is restricted to triangles whose vertices are vertices of the polygon (i.e.
476:
66:
895:
Heinrich-Litan, L.; Lübbecke, M. E. (2007). "Rectangle covers revisited computationally".
377:
is the number of vertices of the polygon. The same is true for a covering by rectilinear
1345:
1406:
691:
557:
1359:
1430:
1375:
1061:
1044:
1028:
1011:
510:
443:
106:
is a covering that does not contain any other covering (i.e. it is a local minimum).
1141:
820:
977:
Keil, J. M. (1986). "Minimally covering a horizontally convex orthogonal polygon".
864:
Proceedings of the sixteenth annual ACM symposium on Theory of computing - STOC '84
716:
661:
556:
Covering a polygon with convex polygons is NP-hard even when the target polygon is
397:
378:
220:
926:
1198:
O'Rourke, J.; Supowit, K. (1983). "Some NP-hard polygon decomposition problems".
1171:
319:
Even when the target polygon is only half-orthogonally convex (i.e. only in the
687:
Covering a polygon (which may contain holes) with spiral polygons is NP-hard.
1133:
979:
Proceedings of the second annual symposium on
Computational geometry - SCG '86
963:
752:
216:
1383:
1259:
1211:
1162:
Christ, T. (2011). "Beyond
Triangulation: Covering Polygons with Triangles".
1045:"Covering orthogonal polygons with star polygons: The perfect graph approach"
1095:
918:
802:
1358:
Fowler, Robert J.; Paterson, Michael S.; Tanimoto, Steven L. (1981-06-13).
95:
is a collection of maximal units, possibly overlapping, whose union equals
871:
561:
431:
The problem of covering a polygon with star polygons is a variant of the
198:
For polygons which may contain holes, finding a minimum such covering is
20:
986:
1166:. Lecture Notes in Computer Science. Vol. 6844. pp. 231–242.
199:
28:
793:
Culberson, J. C.; Reckhow, R. A. (1988). "Covering polygons is hard".
438:
The visibility graph for the problem of minimally covering hole-free
1012:"Orthogonally convex coverings of orthogonal polygons without holes"
848:
323:
direction), a minimum covering by rectangles can be found in time O(
1336:
219:. A general polygon is analogous to a general graph. Just like the
1254:. Lecture Notes in Computer Science. Vol. 2161. p. 333.
741:
International
Journal of Computational Geometry & Applications
450:
Covering a polygon without acute angles with squares or rectangles
190:
1080:. Lecture Notes in Computer Science. Vol. 1269. p. 27.
47:, find a smallest set of squares whose union equals the polygon.
676:
353:
Covering a rectilinear polygon with orthogonally convex polygons
337:
For rectilinear polygons which may contain holes, there is an O(
1301:
Abrahamsen, Mikkel; Adamaszek, Anna; Miltzow, Tillmann (2017),
1078:
1360:"Optimal packing and covering in the plane are NP-complete"
263:
The number of squares in the resulting covering is at most
252:
from the polygon, then glue back two overlapping copies of
259:
Now use the original algorithm to find a minimum covering.
287:. Hence the number of squares in the covering is at most
795:
29th Annual
Symposium on Foundations of Computer Science
1309:
589:
530:
459:
Covering a polygon with rectangles of a finite family
277:
is the number of holes. It is possible to prove that
361:
which is half-orthogonally convex (i.e. only in the
80:
A polygon covering problem is a special case of the
16:
Set of primitive shapes whose union equals a polygon
490:are not allowed), then the problem is NP-complete.
1320:
600:
541:
780:Prof. Reuven Bar-Yehuda in personal communication
768:Proc. 26th Allerton Conf. Commun. Control Comput.
392:Covering a rectilinear polygon with star polygons
77:their union must be equal to the target polygon.
31:is a set of primitive units (e.g. squares) whose
1043:Motwani, R.; Raghunathan, A.; Saran, H. (1990).
582:Covering a simple polygon with star polygons is
237:is the number of squares in a minimum covering:
614:Covering a set of points with identical squares
837:SIAM Journal on Algebraic and Discrete Methods
298:Covering a rectilinear polygon with rectangles
1397:Keil, J. M. (2000). "Polygon Decomposition".
245:connecting the hole to the external boundary.
73:problem, in which the units must be disjoint
8:
181:is a one-knob continuator, then remove from
1122:Computational Optimization and Applications
675:is NP-hard; the proof is by reduction from
117:Covering a rectilinear polygon with squares
652:of these squares. Note that two points in
1335:
1314:
1313:
1308:
1085:
1060:
1027:
953:
908:
594:
593:
588:
535:
534:
529:
331:is the number of vertices of the polygon.
734:
732:
697:Additional information can be found in.
671:. Finding a smallest square-covering of
1245:
1243:
1200:IEEE Transactions on Information Theory
1193:
1191:
1049:Journal of Computer and System Sciences
1016:Journal of Computer and System Sciences
728:
520:Covering a polygon with convex polygons
1157:
1155:
1153:
1151:
1010:Culberson, J.; Reckhow, R. A. (1989).
788:
786:
572:Covering a polygon with star polygons
7:
1321:{\displaystyle \exists \mathbb {R} }
897:Journal of Experimental Algorithmics
601:{\displaystyle \exists \mathbb {R} }
542:{\displaystyle \exists \mathbb {R} }
1399:Handbook of Computational Geometry
1310:
1227:"Covering Polygons is Even Harder"
590:
531:
493:If Steiner points are not allowed
365:direction), a minimum covering by
54:) or its vertices (this is called
14:
467:Covering a polygon with triangles
347:) factor approximation algorithm.
1407:10.1016/B978-044482537-7/50012-7
369:polygons can be found in time O(
1364:Information Processing Letters
1164:Algorithms and Data Structures
637:, we put a square centered at
549:-complete. There is an O(log
1:
629:Suppose that, for each point
241:For each hole, find a square
159:is not yet covered, then add
1376:10.1016/0020-0190(81)90111-3
1172:10.1007/978-3-642-22300-6_20
1062:10.1016/0022-0000(90)90017-f
1029:10.1016/0022-0000(89)90043-3
408:, such that for every point
1303:The Art Gallery Problem is
553:) approximation algorithm.
1468:
575:
1134:10.1007/s10589-009-9258-1
964:10.1137/s0097539799358835
942:SIAM Journal on Computing
753:10.1142/S021819599600006X
1260:10.1007/3-540-44676-1_28
1212:10.1109/tit.1983.1056648
1110:, Grazyna Zwozniak, 1998
690:Covering a polygon with
442:with star polygons is a
37:polygon covering problem
1096:10.1007/3-540-63248-4_3
919:10.1145/1187436.1216583
803:10.1109/sfcs.1988.21976
694:has also been studied.
56:polygon vertex covering
1437:Computational geometry
1322:
602:
543:
483:is a 3-approximation.
195:
166:Remove the balcony of
41:computational geometry
35:equals the polygon. A
1323:
1252:Algorithms — ESA 2001
872:10.1145/800057.808678
603:
544:
481:polygon triangulation
475:If the polygon is in
194:
52:polygon edge covering
1452:NP-complete problems
1401:. pp. 491–518.
1307:
1284:"Program- FOCS 2023"
1225:Abrahamsen, Mikkel.
587:
528:
440:rectilinear polygons
1346:2017arXiv170406969A
987:10.1145/10515.10520
712:Art gallery problem
660:is equivalent to a
578:Art gallery problem
433:art gallery problem
420:polygon containing
418:orthogonally convex
404:containing a point
367:orthogonally convex
359:rectilinear polygon
310:orthogonally convex
177:If what remains of
123:rectilinear polygon
45:rectilinear polygon
1318:
981:. pp. 43–51.
683:Other combinations
650:intersection graph
598:
568:are not allowed).
539:
497:the polygon is in
196:
139:continuator square
130:While the polygon
1447:Covering problems
1269:978-3-540-42493-2
1181:978-3-642-22299-3
1105:978-3-540-63248-1
812:978-0-8186-0877-3
707:Covering problems
82:set cover problem
71:polygon partition
1459:
1421:
1420:
1394:
1388:
1387:
1355:
1349:
1348:
1339:
1327:
1325:
1324:
1319:
1317:
1298:
1292:
1291:
1280:
1274:
1273:
1247:
1238:
1237:
1231:
1222:
1216:
1215:
1195:
1186:
1185:
1159:
1146:
1145:
1117:
1111:
1109:
1089:
1073:
1067:
1066:
1064:
1040:
1034:
1033:
1031:
1007:
1001:
1000:
974:
968:
967:
957:
937:
931:
930:
912:
892:
886:
885:
859:
853:
852:
832:
826:
824:
790:
781:
778:
772:
771:
763:
757:
756:
736:
607:
605:
604:
599:
597:
548:
546:
545:
540:
538:
499:general position
477:general position
346:
345:
293:
286:
272:
232:
163:to the covering.
111:minimum covering
104:minimal covering
98:
94:
63:covering problem
1467:
1466:
1462:
1461:
1460:
1458:
1457:
1456:
1427:
1426:
1425:
1424:
1417:
1396:
1395:
1391:
1357:
1356:
1352:
1305:
1304:
1300:
1299:
1295:
1282:
1281:
1277:
1270:
1249:
1248:
1241:
1229:
1224:
1223:
1219:
1197:
1196:
1189:
1182:
1161:
1160:
1149:
1119:
1118:
1114:
1106:
1075:
1074:
1070:
1042:
1041:
1037:
1009:
1008:
1004:
997:
976:
975:
971:
939:
938:
934:
894:
893:
889:
882:
866:. p. 167.
861:
860:
856:
849:10.1137/0602042
834:
833:
829:
813:
797:. p. 601.
792:
791:
784:
779:
775:
765:
764:
760:
738:
737:
730:
725:
703:
692:pseudotriangles
685:
670:
647:
616:
585:
584:
580:
574:
526:
525:
522:
469:
461:
452:
394:
355:
350:
340:
338:
300:
288:
278:
264:
233:squares, where
227:
119:
96:
92:
67:packing problem
17:
12:
11:
5:
1465:
1463:
1455:
1454:
1449:
1444:
1439:
1429:
1428:
1423:
1422:
1415:
1389:
1370:(3): 133–137.
1350:
1316:
1312:
1293:
1275:
1268:
1239:
1217:
1187:
1180:
1147:
1112:
1104:
1087:10.1.1.22.9094
1068:
1035:
1002:
996:978-0897911948
995:
969:
955:10.1.1.20.2664
932:
910:10.1.1.69.4576
887:
881:978-0897911337
880:
854:
827:
811:
782:
773:
758:
727:
726:
724:
721:
720:
719:
714:
709:
702:
699:
684:
681:
668:
645:
615:
612:
596:
592:
576:Main article:
573:
570:
566:Steiner points
537:
533:
521:
518:
488:Steiner points
468:
465:
460:
457:
451:
448:
416:, there is an
396:A rectilinear
393:
390:
354:
351:
349:
348:
335:
332:
317:
314:anti rectangle
305:
299:
296:
261:
260:
257:
246:
213:
212:
208:
189:
188:
187:
186:
175:
164:
149:
134:is not empty:
118:
115:
15:
13:
10:
9:
6:
4:
3:
2:
1464:
1453:
1450:
1448:
1445:
1443:
1440:
1438:
1435:
1434:
1432:
1418:
1416:9780444825377
1412:
1408:
1404:
1400:
1393:
1390:
1385:
1381:
1377:
1373:
1369:
1365:
1361:
1354:
1351:
1347:
1343:
1338:
1333:
1329:
1297:
1294:
1289:
1285:
1279:
1276:
1271:
1265:
1261:
1257:
1253:
1246:
1244:
1240:
1235:
1228:
1221:
1218:
1213:
1209:
1205:
1201:
1194:
1192:
1188:
1183:
1177:
1173:
1169:
1165:
1158:
1156:
1154:
1152:
1148:
1143:
1139:
1135:
1131:
1127:
1123:
1116:
1113:
1107:
1101:
1097:
1093:
1088:
1083:
1079:
1072:
1069:
1063:
1058:
1054:
1050:
1046:
1039:
1036:
1030:
1025:
1021:
1017:
1013:
1006:
1003:
998:
992:
988:
984:
980:
973:
970:
965:
961:
956:
951:
947:
943:
936:
933:
928:
924:
920:
916:
911:
906:
902:
898:
891:
888:
883:
877:
873:
869:
865:
858:
855:
850:
846:
842:
838:
831:
828:
822:
818:
814:
808:
804:
800:
796:
789:
787:
783:
777:
774:
769:
762:
759:
754:
750:
746:
742:
735:
733:
729:
722:
718:
715:
713:
710:
708:
705:
704:
700:
698:
695:
693:
688:
682:
680:
678:
674:
667:
663:
659:
655:
651:
644:
640:
636:
632:
627:
625:
621:
613:
611:
609:
579:
571:
569:
567:
563:
560:. It is also
559:
554:
552:
519:
517:
514:
513:for example.
512:
511:Star of David
508:
504:
500:
496:
491:
489:
484:
482:
478:
473:
466:
464:
458:
456:
449:
447:
445:
444:perfect graph
441:
436:
434:
429:
427:
423:
419:
415:
411:
407:
403:
400:is a polygon
399:
391:
389:
387:
382:
380:
379:star polygons
376:
372:
368:
364:
360:
352:
344:
336:
333:
330:
326:
322:
318:
315:
311:
307:
306:
304:
297:
295:
292:
285:
281:
276:
271:
267:
258:
255:
251:
247:
244:
240:
239:
238:
236:
231:
224:
222:
218:
209:
205:
204:
203:
201:
193:
184:
180:
176:
173:
169:
165:
162:
158:
154:
150:
147:
143:
140:
136:
135:
133:
129:
128:
127:
124:
116:
114:
112:
107:
105:
100:
91:of a polygon
90:
85:
83:
78:
76:
72:
68:
64:
59:
57:
53:
48:
46:
42:
38:
34:
30:
26:
22:
1398:
1392:
1367:
1363:
1353:
1302:
1296:
1287:
1278:
1251:
1233:
1220:
1203:
1199:
1163:
1125:
1121:
1115:
1077:
1071:
1052:
1048:
1038:
1019:
1015:
1005:
978:
972:
945:
941:
935:
900:
896:
890:
863:
857:
840:
836:
830:
794:
776:
767:
761:
744:
740:
717:Tessellation
696:
689:
686:
672:
665:
662:clique cover
657:
653:
642:
638:
634:
630:
628:
623:
619:
618:Given a set
617:
581:
555:
550:
523:
515:
506:
502:
494:
492:
485:
474:
470:
462:
453:
437:
430:
425:
421:
413:
409:
405:
401:
398:star polygon
395:
385:
383:
374:
370:
362:
356:
342:
328:
324:
320:
301:
290:
283:
279:
274:
269:
265:
262:
253:
249:
242:
234:
229:
225:
221:vertex cover
214:
197:
182:
178:
171:
167:
160:
156:
145:
141:
131:
120:
110:
108:
103:
101:
88:
86:
79:
74:
60:
55:
51:
49:
36:
24:
18:
948:(6): 1509.
373:^2), where
1431:Categories
1337:1704.06969
1206:(2): 181.
1128:(3): 675.
1022:(2): 166.
843:(4): 394.
747:: 79–102.
723:References
217:tree graph
211:remainder.
1384:0020-0190
1328:-complete
1311:∃
1288:FOCS 2023
1234:IEEE-FOCS
1082:CiteSeerX
1055:: 19–48.
950:CiteSeerX
905:CiteSeerX
770:: 97–106.
608:-complete
591:∃
558:hole-free
532:∃
327:), where
137:Select a
1442:Polygons
1142:15599243
821:34508387
701:See also
562:APX-hard
273:, where
89:covering
25:covering
21:geometry
1342:Bibcode
1290:. IEEE.
903:: 2.6.
648:be the
339:√
200:NP-hard
153:balcony
151:If the
29:polygon
1413:
1382:
1266:
1178:
1140:
1102:
1084:
993:
952:
927:619557
925:
907:
878:
819:
809:
641:. Let
357:For a
207:graph.
1332:arXiv
1230:(PDF)
1138:S2CID
923:S2CID
817:S2CID
284:holes
275:holes
270:holes
170:from
61:In a
33:union
27:of a
1411:ISBN
1380:ISSN
1264:ISBN
1176:ISBN
1100:ISBN
991:ISBN
876:ISBN
807:ISBN
677:3SAT
505:log
424:and
341:log
248:Cut
23:, a
1403:doi
1372:doi
1256:doi
1208:doi
1168:doi
1130:doi
1092:doi
1057:doi
1024:doi
983:doi
960:doi
915:doi
868:doi
845:doi
799:doi
749:doi
664:of
633:in
626:.
495:and
412:in
388:).
308:In
291:opt
280:opt
266:opt
235:opt
230:opt
155:of
144:in
75:and
58:).
19:In
1433::
1409:.
1378:.
1368:12
1366:.
1362:.
1340:,
1330:,
1286:.
1262:.
1242:^
1232:.
1204:29
1202:.
1190:^
1174:.
1150:^
1136:.
1126:48
1124:.
1098:.
1090:.
1053:40
1051:.
1047:.
1020:39
1018:.
1014:.
989:.
958:.
946:32
944:.
921:.
913:.
901:11
899:.
874:.
839:.
815:.
805:.
785:^
745:06
743:.
731:^
679:.
435:.
428:.
381:.
294:.
289:2
282:≥
268:+
228:2
121:A
109:A
102:A
99:.
87:A
1419:.
1405::
1386:.
1374::
1344::
1334::
1315:R
1272:.
1258::
1236:.
1214:.
1210::
1184:.
1170::
1144:.
1132::
1108:.
1094::
1065:.
1059::
1032:.
1026::
999:.
985::
966:.
962::
929:.
917::
884:.
870::
851:.
847::
841:2
825:.
823:.
801::
755:.
751::
673:S
669:S
666:G
658:S
654:S
646:S
643:G
639:p
635:S
631:p
624:S
620:S
595:R
551:n
536:R
507:n
503:n
426:q
422:p
414:P
410:q
406:p
402:P
386:n
375:n
371:n
363:x
343:n
329:n
325:n
321:y
254:s
250:s
243:s
183:P
179:s
174:.
172:P
168:s
161:s
157:s
148:.
146:P
142:s
132:P
97:P
93:P
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
