겹치지 않고 직사각형 세트를 덮을 수있는 가장 적은 직사각형을 찾는 알고리즘

겹치지 않고 직사각형 세트를 덮을 수있는 가장 적은 직사각형을 찾는 알고리즘

---

사각형 세트가 있고 세트를 "축소"하여 원래 세트와 동일한 영역을 설명 할 수있는 사각형 수가 가장 적습니다. 가능하다면 빠른 속도를 원하지만 가능한 한 사각형 수를 줄이는 데 더 관심이 있습니다. 나는 지금 대부분의 시간에 작동하는 접근 방식을 가지고 있습니다.

현재는 가장 왼쪽 상단의 직사각형에서 시작하여 직사각형을 유지하면서 오른쪽 아래로 확장 할 수 있는지 확인합니다. 더 이상 확장 할 수 없을 때까지이를 수행하고 교차하는 모든 사각형을 제거 및 분할 한 다음 확장 된 사각형을 목록에 다시 추가합니다. 그런 다음 다음으로 가장 왼쪽 상단 직사각형으로 프로세스를 다시 시작합니다. 그러나 어떤 경우에는 작동하지 않습니다. 예를 들면 :

이 세 개의 직사각형 세트를 사용하면 올바른 솔루션은 다음과 같이 두 개의 직사각형으로 끝납니다.

그러나이 경우 내 알고리즘은 파란색 사각형을 처리하는 것으로 시작됩니다. 이렇게하면 아래쪽으로 확장되고 노란색 사각형이 올바르게 분할됩니다. 그러나 노란색 사각형의 나머지 부분이 처리되면 아래쪽으로 확장되는 대신 오른쪽으로 먼저 확장되고 이전에 분리 된 부분을 되돌립니다. 그런 다음 마지막 사각형이 처리되고 오른쪽 또는 아래로 확장 할 수 없으므로 원래 사각형 집합이 남아 있습니다. 알고리즘을 조정하여 먼저 확장 한 다음 오른쪽으로 확장 할 수 있습니다. 이것은이 경우를 고칠 수 있지만 뒤집힌 유사한 시나리오에서 동일한 문제를 일으킬 것입니다.

편집 : 명확히하기 위해, 원래의 직사각형 세트는 겹치지 않으며 연결될 필요가 없습니다. 그리고 직사각형의 하위 집합이 연결되면 완전히 덮는 다각형에 구멍이 생길 수 있습니다.

---

귀하의 질문에 대한 제목에도 불구하고 실제로 직선 다각형의 직사각형으로 최소한의 해부 를 찾고 있다고 생각합니다 . (Jason의 링크는 직사각형에 의한 최소 커버 에 관한 것이며 이는 상당히 다른 문제입니다.)

David Eppstein 은 2010 년 설문 조사 기사 Graph-Theoretic Solutions to Computational Geometry Problems 의 섹션 3에서이 문제에 대해 논의 하고 mathoverflow.net의이 답변에서 멋진 요약을 제공합니다 .

아이디어는 끝점으로 두 개의 오목한 정점이있는 분리 된 축 평행 대각선의 최대 수를 찾고이를 따라 분할 한 다음 나머지 오목한 정점에 대해 하나 이상의 분할을 형성하는 것입니다. 분리 된 축 평행 대각선의 최대 수를 찾으려면 대각선의 교차 그래프를 형성하십시오. 이 그래프는이 분형이므로 그래프 매칭 기술을 통해 다항식 시간에서 최대 독립 집합을 찾을 수 있습니다.

다음은 Eppstein의 기사에서 그림 2를 사용하여 훌륭하게 간결한 설명에 대한 나의 글입니다. 구멍이있는 직선 다각형이 있다고 가정합니다.

다각형을 직사각형으로 해부 할 때 각 오목한 정점은 해부의 가장자리 중 하나 이상과 만나야합니다. 따라서 가능한 한 많은 모서리가 이중 작업을 수행하는 경우, 즉 오목한 정점 중 두 개를 연결하는 경우 최소 해부를 얻습니다 .

따라서 완전히 다각형 내에 포함 된 두 개의 오목한 정점 사이에 축 평행 대각선을 그립니다. ( 'Axis-parallel'은 여기서 '수평 또는 수직'을 의미 하고 다각형 의 대각선은 두 개의 인접하지 않은 꼭지점을 연결하는 선입니다.) 우리는 이러한 선을 가능한 한 많이 사용하고 싶습니다. 교차하지 마십시오.

(축 평행 대각선이 없으면 해부가 사소합니다. 각 오목한 정점에서 잘라냅니다. 또는 축 평행 대각선 사이에 교차점이없는 경우 모두 사용하고 나머지 오목한 정점에서 잘라냅니다. . 그렇지 않으면 계속 읽으십시오.)

교차 그래프 선분의 집합의 모든 선분에 대한 노드를 가지며, 선이 교차하는 경우에는 두 에지 노드를 결합한다. 축 평행 대각선에 대한 교차 그래프는 다음과 같습니다.

그것은의 양자 한 부분에서 수직 대각선, 다른 부분에 수평 대각선으로. 이제 우리는 교차하지 않는 한 가능한 한 많은 대각선을 선택하려고합니다. 이것은 교차 그래프에서 최대 독립 세트 를 찾는 것에 해당합니다 .

Finding the maximum independent set in a general graph is an NP-hard problem, but in the special case of a bipartite graph, König’s theorem shows that it’s equivalent to the problem of finding a maximum matching, which can be solved in polynomial time, for example by the Hopcroft–Karp algorithm. A given graph can have several maximum matchings, but any of them will do, as they all have the same size. In the example, all the maximum matchings have three pairs of vertices, for example {(2, 4), (6, 3), (7, 8)}:

(Other maximum matchings in this graph include {(1, 3), (2, 5), (7, 8)}; {(2, 4), (3, 6), (5, 7)}; and {(1, 3), (2, 4), (7, 8)}.)

To get from a maximum matching to the corresponding minimum vertex cover, apply the proof of König’s theorem. In the matching shown above, the left set is L = {1, 2, 6, 7}, the right set is R = {3, 4, 5, 8}, and the set of unmatched vertices in L is U = {1}. There is only one alternating path starting in U, namely 1–3–6, so the set of vertices in alternating paths is Z = {1, 3, 6} and the minimum vertex cover is thus K = (L \ Z) ∪ (R ∩ Z) = {2, 3, 7}, shown in red below, with the maximum independent set in green:

이것을 다시 해부 문제로 변환하면 해부에서 5 개의 축 평행 대각선을 사용할 수 있습니다.

마지막으로 나머지 오목한 정점에서 잘라내어 해부를 완료합니다.

참고 URL : https://stackoverflow.com/questions/5919298/algorithm-for-finding-the-fewest-rectangles-to-cover-a-set-of-rectangles-without