폴리곤 피복

Polygon covering

폴리곤 피복은 조합이 폴리곤과 동일한 원시 단위(예: 제곱)의 집합이다.폴리곤 커버 문제는 주어진 폴리곤에 대해 최소 단위 수로 커버를 찾는 문제다.이것은 계산 기하학에서 중요한 문제들이다.덮고 있는 폴리곤의 종류에 따라 여러 가지 폴리곤 커버 문제가 있다.폴리곤 커버 문제의 예: 직선으로 된 폴리곤이 주어진 경우, 결합이 폴리곤과 동일한 최소 제곱 세트를 찾으십시오.

일부 시나리오에서는 폴리곤 전체를 덮을 필요가 없고, 폴리곤의 가장자리(이것을 폴리곤 가장자리 커버라고 한다) 또는 정점(이것을 폴리곤 꼭지 커버라고 한다)만 덮을 필요가 있다.

피복 문제에서 피복 단위가 목표 폴리곤과 정확히 동일한 경우 피복 단위가 중복될 수 있다.이는 단위가 분리되어야 하고 조합이 목표 폴리곤보다 작을 수 있는 포장 문제, 단위가 분리되어야 하고 조합이 목표 폴리곤과 같아야 하는 폴리곤 파티션 문제와 대조적이다.

폴리곤 커버 문제는 세트 커버 문제의 특별한 경우다.일반적으로 가장 작은 세트 커버를 찾는 문제는 NP-완전하지만, 폴리곤의 특수 등급의 경우 가장 작은 폴리곤 시간이다.

폴리곤 P의 피복은 겹칠 수 있는 최대 단위들의 집합이며, 결합은 P와 같다.

최소 커버는 다른 커버를 포함하지 않는 커버(즉, 국소 최소 커버)이다.

최소 커버는 최소 단위 수(즉, 전지구적 최소 단위)로 커버하는 것이다.모든 최소 커버력은 미미하지만, 그 반대는 아니다.

정사각형으로 직사각형 다각형 덮기

직선형 다각형은 항상 다각형의 한정된 정점 수로 덮을 수 있다.[1]알고리즘은 국부적 최적화 접근방식을 사용한다. 즉, 커버에 필수적인 최대 제곱을 반복적으로 선택한 다음(즉, 다른 최대 제곱에서 다루지 않는 노출된 점을 포함) 불필요하게 되는 점을 폴리곤에서 삭제함으로써 커버를 구축한다(즉, 미래 제곱을 지원하기 위해 필요하지 않음).다음은 알고리즘의 단순화된 유사 코드:

  • 다각형 P가 비어 있지 않은 경우:
    • P에서 연속기 사각 s를 선택하십시오.
    • s의 발코니가 아직 덮이지 않은 경우 덮개에 s를 추가한다.
    • 의 발코니를 P에서 제거한다.
    • s가 1노브 연속기일 경우 P에서 노브에 인접한 특정 사각형을 제거하여 향후 사각형에 충분한 보안 거리를 두도록 주의하십시오.
Removing holes from a rectilinear polygon.png

구멍이 있을 수 있는 폴리곤의 경우 그러한 덮개를 최소로 찾는 것은 NP-하드다.[2]구멍 없는 폴리곤과 일반 폴리곤의 이 날카로운 차이는 직선으로 된 폴리곤의 최대 제곱과 비방향 그래프의 노드 사이의 다음과 같은 유추를 바탕으로 직관적으로 설명할 수 있다.[1]

  • 일부 최대 제곱은 폴리곤의 경계와 연속적인 교차점을 가지며, 제거해도 나머지 폴리곤은 연결된 상태를 유지한다.이러한 사각형은 "연속기"라고 불리며, 그래프를 분리하지 않고도 제거할 수 있는 리프 노드(가장자리가 하나 있는 노드)와 유사하다.
  • 다른 최대 제곱은 "분리자"이다. 분리할 때 다각형은 분리된 두 개의 다각형으로 갈라진다.이러한 노드는 둘 이상의 가장자리가 있는 노드와 유사하며, 제거될 경우 연결이 끊어진 나머지를 남긴다.

구멍이 없는 직사각형 폴리곤에서, 모든 최대 제곱은 연속기 또는 분리기 중 하나이므로, 그러한 폴리곤은 트리 그래프와 유사하다.일반 다각형은 일반 그래프와 유사하다.나무 그래프의 경우 꼭지점 커버 문제가 다항식이지만 일반 그래프의 경우 NP-hard인 것처럼, 구멍 없는 폴리곤의 경우 사각 커버 문제가 선형이지만 일반 폴리곤의 경우 NP-hard이다.

선형 알고리즘을 사용하여 2-대략을 얻을 수 있다. 즉, 최대 2개의 옵트 스퀘어로 덮는 것으로, 여기서 선택은 최소 커버의 제곱 수입니다.[3]

  • 각 구멍에 대해 구멍과 외부 경계를 연결하는 사각 s를 찾는다.
  • 폴리곤에서 s를 자른 다음, s의 겹치는 두 개의 사본을 다시 접착한다(그림 참조).그 결과 생긴 다각형은 평면형이 아니라 여전히 2차원이고, 현재는 구멍이 없다.
  • 이제 원래의 알고리즘을 사용하여 최소 커버를 찾으십시오.

결과 커버의 사각형 수는 최대 선택 + 구멍이며, 여기서 구멍은 구멍 수입니다.선택 구멍이라는 것을 증명할 수 있다.따라서 덮개의 정사각형 수는 최대 2개 선택이다.

직사각형 폴리곤을 직사각형으로 덮기

일반 직사각형 폴리곤의 경우 대상 폴리곤이 구멍이 없는 경우에도 최소 직사각형 커버를 찾는 문제는 NP-하드다.[4]이 문제에 대해 몇 가지 부분적인 해결책이 제시되었다.

  1. 직교 볼록 폴리곤에서 최소 커버에 있는 직사각형의 수는 반직사각형의 블록 수와 같으며, 이 사실은 직사각형에 의한 최소 커버를 찾기 위한 다항 시간 알고리즘을 구축하는 데 사용될 수 있다.[5]
  2. 대상 폴리곤이 반정형 볼록(즉, y 방향으로만)에 불과한 경우에도 직사각형으로 최소 커버하는 것을 시간 O(n2)에서 찾을 수 있는데, 여기서 n은 폴리곤의 정점수다.[6]
  3. 실제 데이터에 대해 좋은 경험적 결과를 제공하는 근사 알고리즘은 다음을 통해 제시된다.[7]
  4. 구멍이 포함될 수 있는 직사각형 다각형의 경우 O(점수 n) 인자 근사 알고리즘이 있다.[8]

직교 볼록 폴리곤을 직교 볼록 폴리곤으로 덮기

반정형 볼록(즉, x 방향으로만)인 직선형 폴리곤의 경우 직교 볼록 폴리곤에 의한 최소 커버는 시간 O(n^2)에서 찾을 수 있으며, 여기서 n은 폴리곤의 정점 수입니다.직선으로 된 항성 다각형에 의한 커버도 마찬가지다.[9]

최소 덮개 내 직교-콘벡스 구성 요소의 수는 경우에 따라 덮개 자체를 찾지 않고도 시간 O(n) 내에 찾을 수 있다.[10]

항성 다각형으로 직사각형 다각형 덮기

직사각형 항성 폴리곤은 P의 모든 점 Q에 대해 p와 q를 포함하는 직교 볼록형 폴리곤이 있도록 p를 포함하는 폴리곤 P이다.

폴리곤을 별 폴리곤으로 덮는 문제는 미술관 문제의 변형이다.

홀이 없는 직사각형 다각형을 별 다각형으로 최소로 덮는 문제에 대한 가시성 그래프는 완벽한 그래프다.이 완전성 속성은 직선으로 된 항성 다각형이 있는 직선으로 된 폴리곤의 최소 덮개를 찾기 위한 다항 알고리즘을 의미한다.[11]

정사각형 또는 직사각형으로 급성 각도 없이 다각형 덮기

사각형이나 직사각형에 의한 덮개를 찾을 수 있는 가장 일반적인 폴리곤 등급은 급성 내부 각도가 없는 폴리곤 등급이다.이는 예각은 한정된 수의 직사각형으로 덮을 수 없기 때문이다.이 문제는 NP-hard이지만 몇 가지 근사 알고리즘이 존재한다.[12]

유한가족의 직사각형으로 다각형 덮기

경우에 따라 다각형은 임의의 직사각형이 아니라 유한한 가족의 직사각형으로 덮어야 한다.[13]

삼각형으로 다각형 덮기

주어진 다각형을 덮고 있는 가장 작은 삼각형 세트를 찾는 것은 NP-hard이다.또한 근사치가 어렵다 - 모든 다항식 시간 알고리즘은 최소 커버의 크기(1 + 1/19151)를 곱한 커버를 찾을 수 있다.[14]

폴리곤이 일반적 위치(즉, 두 모서리가 시준되지 않음)인 경우, 모든 삼각형은 최대 3개의 폴리곤 가장자리를 포함할 수 있다.따라서 모든 다각형 삼각측량은 3-대략이다.

덮개가 폴리곤의 정점이 되는 삼각형(즉, Steiner 점들은 허용되지 않음)으로 제한되는 경우, 문제는 NP-완전이다.

Steiner 포인트가 허용되지 않고 폴리곤이 일반적인 위치(즉, 두 모서리가 시준되지 않음)에 있는 경우, Steiner 포인트가 없는 모든 최소 커버 역시 폴리곤을 삼각형으로 최소 분할(즉, 최소 커버의 삼각형이 겹치지 않도록)하는 것이다.[14]따라서 최소 피복 문제는 시간 O(nlog n)로 해결할 수 있는 다각형 삼각측량 문제와 동일하다.일반적인 위치 가정을 취하하면 최적의 피복에 있는 삼각형이 겹치는 다각형이 있다는 점에 유의하십시오.예를 들어 다윗의 별을 생각해 보십시오.

삼각형으로 다각형의 경계만 덮는 문제는 NP완전하지만 효율적인 2-추정(two-tarmism)이 있다.[14]

볼록 폴리곤으로 폴리곤 덮기

볼록한 다각형으로 폴리곤(구멍을 포함할 수 있음)을 덮는 것은 NP-강경이다.[15]O(log n) 근사 알고리즘이 있다.[16]

볼록 폴리곤을 볼록 폴리곤으로 덮는 것은 대상 폴리곤이 구멍이 없는 경우에도 NP-하드다.[4]그것은 또한 APX-hard이다.[16]문제는 커버가 새로운 정점을 도입해서는 안 되는 경우(즉, Steiner 포인트가 허용되지 않는 경우) NP-완전이다.[14]

별 다각형으로 다각형 덮기

주요 기사:미술관 문제

단순한 다각형을 별 다각형으로 덮는 것은 -완료, 각 별의 커널에 있는 점이 폴리곤의 가장자리에 포함되어야 하는 버전이다.[17]

동일한 정사각형으로 점 집합 덮기

평면 내 점의 집합 S와 동일한 정사각형 집합의 경우 목표는 S의 모든 점을 포함할 수 있는 최소 제곱 수를 찾는 것이다.

S의 각 점 p에 대해 p를 중심으로 한 정사각형을 배치한다고 가정합시다.G를S 이 정사각형의 교차 그래프로 하자.S의 두 점은 중심에 있는 두 개의 사각형이 겹치는 경우에만 하나의 사각형으로 덮을 수 있다는 점에 유의하십시오.따라서 S의 점들을 정사각형으로 덮는 것은S G의 집단을 덮는 것과 같다. S의 가장 작은 정사각형 덮개를 찾는 것은 NP-hard이다. 그 증거는 3SAT로부터의 축소에 의한 것이다.[18]

기타 조합

나선형으로 폴리곤(구멍을 포함할 수 있음)을 덮는 것은 NP-강경이다.[15]

폴리곤을 가성으로 덮는 것도 연구되었다.

추가 정보는 에서 찾을 수 있다.[19]

참고 항목

참조

  1. ^ 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.
  2. ^ 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.
  3. ^ 루벤 바-예후다 교수 개인소통
  4. ^ 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..
  5. ^ 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.
  6. ^ 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.
  7. ^ 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.
  8. ^ 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.
  9. ^ 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.
  10. ^ 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.
  11. ^ 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.
  12. ^ 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.
  13. ^ 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.
  14. ^ 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.
  15. ^ 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.
  16. ^ 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.
  17. ^ Abrahamsen, Mikkel; Adamaszek, Anna; Miltzow, Tillmann (2017), The Art Gallery Problem is -complete, arXiv:1704.06969, Bibcode:2017arXiv170406969A
  18. ^ 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.
  19. ^ Keil, J. M. (2000). "Polygon Decomposition". Handbook of Computational Geometry. pp. 491–518. doi:10.1016/B978-044482537-7/50012-7. ISBN 9780444825377.