최대 분리 세트

계산 기하학에서 최대 분리형 집합(MDS)은 주어진 후보 형상 집합에서 선택한 가장 큰 비 겹치지 않는 기하학적 형상 집합이다.

겹치지 않는 도형의 모든 집합은 도형의 교차 그래프에서 독립된 집합이다.따라서 MDS 문제는 최대 독립 집합(MIS) 문제의 특수한 경우다.두 문제 모두 NP 완료되었지만 MDS를 찾는 것이 두 가지 측면에서 MIS를 찾는 것보다 더 쉬울 수 있다.

일반적인 MIS 문제의 경우 가장 잘 알려진 정확한 알고리즘은 지수적이다.일부 기하학적 교차로 그래프에는 MDS를 찾기 위한 하위 알고리즘이 있다.^[1]
일반적인 MIS 문제는 근사치가 어렵고 심지어 일정한 요인 근사치조차 가지고 있지 않다.일부 기하학적 교차로 그래프에는 MDS를 찾기 위한 다항식 시간 근사 구성표(PTAS)가 있다.

MDS를 찾는 것은 자동 라벨 배치, VLSI 회로 설계 및 셀룰러 주파수 분할 멀티플렉싱과 같은 응용 분야에서 중요하다.

MDS 문제는 형상별로 다른 가중치를 할당하고 최대 총중량으로 분리 집합을 검색하면 일반화할 수 있다.

다음 텍스트에서 MDS(C)는 C 세트에 설정된 최대 이음매를 나타낸다.

탐욕 알고리즘

형상 모수의 C가 설정되면 MDS(C)에 대한 근사치는 다음과 같은 탐욕 알고리즘을 통해 확인할 수 있다.

초기화: 빈 세트 S를 초기화하십시오.
검색: 모든 형상 모수(C) x에 대해:
1. 계산 N(x) - x(x자체 포함)를 교차하는 C의 모든 형상 부분 집합.
2. 이 하위 집합에서 가장 큰 독립 집합인 MDS(N(x))를 계산하십시오.
3. MDS(N(x))가 최소화되도록 x를 선택하십시오.
S에 x를 추가한다.
C에서 x와 N(x)을 제거한다.
C에 도형이 있으면 Search로 돌아가십시오.
끝: 세트 S를 반환하십시오.

우리가 S에 추가하는 모든 형상 x에 대해, 우리는 N(x)의 형상들이 x와 교차하기 때문에 나중에 S에 추가될 수 없기 때문에 형상을 잃어버린다.그러나 이러한 형상들 중 일부는 그 자체가 서로 교차하며, 따라서 어떤 경우에도 그것들이 모두 최적의 용액 MDS(S)에 있을 가능성은 없다.최적 용액에 모두 포함될 수 있는 도형의 가장 큰 부분 집합은 MDS(N(x))이다.따라서 MDS(N(x))를 최소화하는 x를 선택하면 s에 x를 더하면 손실이 최소화된다.

특히 MDS(N(x))가 상수(예: M)에 의해 경계되는 x가 있다고 보장할 수 있다면, 이 탐욕스러운 알고리즘은 다음과 같이 보장할 수 있듯이 일정한 M-요인 근사치를 산출한다.

$S \geq {\frac { MDS(C) }{M}}$

그러한 상한 M은 다음과 같은 몇 가지 흥미로운 경우에 존재한다.

1차원 구간: 정확한 다항식 알고리즘

C가 선상의 구간 집합인 경우 M=1로, 따라서 탐욕스러운 알고리즘이 정확한 MDS를 찾는다. 이를 보려면 구간이 수직이라고 가정하고 x를 가장 높은 하단 끝점과의 구간으로 한다.x로 교차하는 다른 모든 간격은 아래쪽 끝점을 통과해야 한다.따라서 N(x)의 모든 구간이 교차하며, MDS(N(x))의 크기는 최대 1(그림 참조)이다.

따라서 1차원 사례에서 MDS는 정확히 O(n log n):^[2]

구간을 하단 끝점의 오름차순으로 정렬하십시오(이 작업은 O(n 로그 n) 시간이 소요됨).
가장 높은 하단 끝점의 구간을 추가하고 교차하는 구간을 모두 삭제하십시오.
간격이 남지 않을 때까지 계속한다.

이 알고리즘은 간격 스케줄링 문제에 대한 가장 이른 마감일 첫 번째 스케줄링 솔루션과 유사하다.

1차원 사례와 대조적으로 2차원 이상에서 MDS 문제는 NP-완전성이 되고, 따라서 정확한 초다항식 알고리즘이나 대략적인 다항식 알고리즘을 가지고 있다.

지방 모양: 일정한 요인 근사치

C가 단위 디스크 집합인 경우, M=3은 가장 왼쪽 디스크(중앙이 가장 작은 x 좌표를 가진 디스크)가 다른 디스크 3개에서 교차하기 때문이다(^[3]그림 참조).따라서 탐욕스러운 알고리즘은 최소 MDS(C)/3 크기의 디스조인트 세트를 찾아낸다.

마찬가지로 C가 축-병렬 단위 제곱의 집합인 경우 M=2.

C가 임의 크기 디스크의 집합인 경우, 반경이 가장 작은 디스크가 최대 5개의 다른 분리 디스크와 교차하기 때문에 M=5이다(그림 참조).

마찬가지로 C가 임의 크기 축-병렬 제곱의 집합인 경우 M=4.

다른 일반 다각형에 대해 다른 상수를 계산할 수 있다.^[3]

분할 및 재무 알고리즘

MDS를 찾는 가장 일반적인 접근방식은 분할 및 재무다.이 접근방식의 일반적인 알고리즘은 다음과 같다.

주어진 형상 집합을 둘 이상의 부분 집합으로 나누어서 기하학적 고려 때문에 각 부분 집합의 형상들이 다른 부분 집합의 형상들과 겹칠 수 없도록 한다.
각 서브셋에서 MDS를 개별적으로 재귀적으로 찾으십시오.
모든 하위 집합에서 MDS 결합을 반환하십시오.

이 접근법의 주요 과제는 세트를 하위 집합으로 나누는 기하학적 방법을 찾는 것이다.이는 다음 하위 절에서 설명한 대로 하위 집합 중 하나에 맞지 않는 소수의 형상을 폐기해야 할 수 있다.

높이가 같은 축-병렬 직사각형: 2-근

C를 평면에 축-병렬 직사각형 집합으로 하고, 모두 높이 H는 같으나 길이는 다양하다.다음 알고리즘은 시간 O(n log n)에서 최소 MDS(C) /2 크기의 디스조인트 세트를 찾는다.^[2]

다음과 같이 m 수평선을 그리십시오.
1. 두 선 사이의 분리는 엄밀히 말하면 H보다 많다.
2. 각 선은 적어도 하나의 직사각형을 교차한다(헨체 m ≤ n).
3. 각 직사각형은 정확히 하나의 선으로 교차한다.
모든 직사각형의 높이가 H이기 때문에 직사각형이 둘 이상의 선으로 교차하는 것은 불가능하다.따라서 직사각형 세트를 m 하위 집합으로 분할한다( $R_{i},\ldots ,R_{m}$ , $R_{i},\ldots ,R_{m}$ … $R_{i},\ldots ,R_{m}$ , $R_{i},\ldots ,R_{m}$ $R_{i},\ldots ,R_{m}$ ${\$ – 각 하위 집합은 단일 선으로 교차하는 직사각형을 포함한다.
각 부분 집합 $R_{i}$ ${\$ ${$ $i}}$ 에 대해 1차원 탐욕 알고리즘(위 참조 $M_{i}$ )을 $M_{i}$ 하여 정확한 MDS M i {\displaystyle $M_{i}}$ 를 계산하십시오 $R_{i}$
시공에 의해 ( $R_{i}$ ${\$ 의 사각형만 $R_{i+1}$ $R_{i+1}$ $R_{i+1}$ {\ $displaystyle R_{i$ $+$ 1} $R_{i-1}$ $R_{i-1}$ - $R_{i-1}$ {\ $displaystyle R_{i-1$ }에서 교차할 수 있다 $R_{i-1}$ 따라서 다음의 두 조합은 각각 분리 집합이다.
- 홀수 MDS 조합: $M_{1}\cup M_{3}\cup \cdots$ $M_{1}\cup M_{3}\cup \cdots$ ∪ M $M_{1}\cup M_{3}\cup \cdots$ $M_{1}\cup M_{3}\cup \cdots$ $M_{1}\cup M_{3}\cup \cdots$ $M_{1}\컵 M_{3}\컵 \cdots$
- 짝수 MDS 연합: $M_{2}\cup M_{4}\cup \cdots$ $M_{2}\cup M_{4}\cup \cdots$ $M_{2}\cup M_{4}\cup \cdots$ M $M_{2}\cup M_{4}\cup \cdots$ $M_{2}\cup M_{4}\cup \cdots$ $M_{2}\cup M_{4}\cup \cdots$ $M_{2}\컵 M_{4}\컵 \cdots$
이 두 조합 중 가장 큰 조합은 반납하십시오.크기는 MDS /2 이상이어야 한다.

높이가 같은 축 평행 직사각형: PTAS

C를 평면에 축-병렬 직사각형 집합으로 하고, 모든 높이는 같지만 길이는 다르다.모든 상수 k > 1에 대해 시간 O(n^2k−1)에서 최소 MDS(C) /(1 + 1/k) 크기의 디스조인트 세트를 찾는 알고리즘이 있다.^[2]

알고리즘은 동적인 프로그래밍과 호크바움, 마아스의 시프트 기법을 결합하여 위에서 언급한 2-대략의 개선이다.^[4]

이 알고리즘은 d차원으로 일반화할 수 있다.라벨의 크기가 한 치수를 제외한 모든 치수에 동일한 경우, 치수 중 하나를 따라 동적 프로그래밍을 적용하면 유사한 근사치를 찾을 수 있다.이것은 또한 시간을 n^O(1/e)로 줄인다.^[5]

축-병렬 직사각형: 로그-인자 근사

C를 평면의 n축 평행 직사각형 집합으로 한다.다음 알고리즘은 시간 O $($ $O(n\log {n})$ $O(n\log {n})$ n $O(n\log {n})$ )에서 ${\frac {|MDS(C)|}{\log {n}}}$ 최소 M ${\frac {|MDS(C)|}{\log {n}}}$ ${\frac {|MDS(C)|}{\log {n}}}$ ( ${\frac {|MDS(C)|}{\log {n}}}$ ) ${\frac {|MDS(C)|}{\log {n}}}$ ${\frac {|MDS(C)|}{\log {n}}}$ ${\$ {\ $frac(C)}{\$ $displaystyle O(n\log {n}})$ 크기의 디스조인트 세트를 찾는다 $O(n\log {n})$ ^[2]

초기화: 주어진 직사각형의 수평 가장자리는 y 좌표를 기준으로 정렬하고 수직 가장자리는 x 좌표를 기준으로 정렬한다(이 단계에는 시간 O(n log n)).
정지 조건: 최대 n ≤ 2 도형이 있는 경우 MDS를 직접 계산하고 반환하십시오.
재귀 부품:
1. $x_{\mathrm {med} }$ $x_{\mathrm {med} }$ $x_{\mathrm {med} }$ $x_{\mathrm {med} }$ ${\$ 을(를) 중위수 x 좌표로 한다 $x_{\mathrm {med} }$ .
2. Partition the input rectangles into three groups according to their relation to the line $x=x_{\mathrm {med} }$ : those entirely to its left ( $R_{\mathrm {left} }$ ), those entirely to its right ( $R_{\mathrm {right} }$ ), and those int그것에 의해 왜곡되었다( $R_{\mathrm {int} }$ $R_{\mathrm {int} }$ ${\$ 시공별로 $R_{\mathrm {left} }$ $R_{\mathrm {left} }$ $R_{\mathrm {left} }$ e $R_{\mathrm {left} }$ t ${\$ 과 $R_{{\mathrm {left}}}$ ( $R_{\mathrm {right} }$ ) $R_{\mathrm {right} }$ $R_{\mathrm {right} }$ $R_{\mathrm {right} }$ h $R_{\mathrm {right} }$ t {\ $displaystyle$ R_{\ $mathrm$ { $right}}$ 의 기본값은 최대 n/2이다 $R_{\mathrm {right} }$ .
3. Recursively compute an approximate MDS in $R_{\mathrm {left} }$ ( $M_{\mathrm {left} }$ ) and in $R_{\mathrm {right} }$ ( $M_{\mathrm {right} }$ ), and calculate their union.By construction, the rectangles in $M_{\mathrm {left} }$ and $M_{\mathrm {right} }$ are all disjoint, so $M_{\mathrm {left} }\cup M_{\mathrm {right} }$ is a disjoint set.
4. $M_{\mathrm {int} }$ t ${\$ Min $R_{\mathrm {int} }$ t ${\$ {int} $})$ 에서 정확한 MDS를 계산하십시오. $M_{\mathrm {int} }$ $R_{\mathrm {int} }$ $R_{\mathrm {int} }$ ${\$ 의 모든 직사각형이 단일 $x=x_{\mathrm {med} }$ $x=x_{\mathrm {med} }$ = $x=x_{\mathrm {med} }$ e $x=x_{\mathrm {med} }$ ${\$ x $=x_{\mathrm$ { $med$ 을 $R_{{\mathrm {int}}}$ 교차하므로 이 계산은 일련의 구간에서 MDS를 찾는 것과 동등하며, O(위의 시간 내에 정확하게 해결할 수 있다.
$M_{\mathrm {left} }\cup M_{\mathrm {right} }$ $M_{\mathrm {left} }\cup M_{\mathrm {right} }$ e $M_{\mathrm {left} }\cup M_{\mathrm {right} }$ t $M_{\mathrm {left} }\cup M_{\mathrm {right} }$ $M_{\mathrm {left} }\cup M_{\mathrm {right} }$ r i $M_{\mathrm {left} }\cup M_{\mathrm {right} }$ $M_{\mathrm {left} }\cup M_{\mathrm {right} }$ ${\$ $M_{\mathrm {int} }$ $M_{\mathrm {int} }$ n $M_{\mathrm {int} }$ {\ $displaystym M_{\mathrm$ {int $}}}}}}}}}$ 중 더 큰 것을 반환하십시오.

It is provable by induction that, at the last step, either $M_{\mathrm {left} }\cup M_{\mathrm {right} }$ or $M_{\mathrm {int} }$ have a cardinality of at least ${\frac { MDS(C) }{\log {n}}}$ .

근사계수는 $O(\log {\log {n}})$ $O(\log {\log {n}})$ $O(\log {\log {n}})$ $){\displaystyle$ O $(\log {\log {n})$ 로 감소하고 $O(\log {\log {n}})$ ^[6] 직사각형의 가중치가 다른 경우로 일반화했다.^[7]

축-병렬 직사각형: 상수 요인 근사

긴 시간 동안 길이와 높이가 다른 축 평행 직사각형에 대해 일정한 요인 근사치가 존재하는지 여부는 알려지지 않았다.단두대 컷을 이용해 이런 근사치를 찾을 수 있을 것이라는 추측이 나왔다.특히 $\Omega (n)$ ( $\Omega (n)$ $\Omega (n)$ $\Oomega (n)$ 개의 $\Omega (n)$ 직사각형이 분리되는 축-병행 직사각형의 단두대 분리가 존재하는 경우 동적 프로그래밍 접근법에 사용하여 MDS에 대한 일정한 요인 근사치를 찾을 수 있다.^[8]^{: sub.1.2}

현재까지 이 같은 단두대 분리가 존재하는지 여부는 알려지지 않았다.그러나, Joseph S. B. Mitchell은 특별한 종류의 비구두절단을 사용하는 일정한 요인 근사 알고리즘을 제시하였다.^[9]

크기가 동일한 뚱뚱한 물체: PTAS

C는 같은 크기의 정사각형이나 원들의 집합이 되게 하라.간단한 시프트-그리드 전략을 사용하여 MDS를 찾기 위한 다항식 시간 근사 방법이 있다.시간 n 시간^O(1/e²) 및 선형 공간의 최대값(1 - e) 내에서 솔루션을 찾는다.^[4]전략은 대략 같은 크기의 지방 개체의 집합(즉, 최대 대 최소 크기 비율이 상수에 의해 제한되는 경우)으로 일반화한다.

임의 크기의 뚱뚱한 개체: PTAS

C를 임의 크기의 n개의 지방 개체(예: 사각형 또는 원) 집합으로 한다.다단계 그리드 정렬을 기반으로 MDS를 찾기 위한 PTAS가 있다.그것은 거의 동시에 두 그룹에 의해 발견되었고, 두 가지 다른 방법으로 설명되었다.

버전 1

버전 1은 모든 상수 k > 1에 대해 시간 n에서^O(k²) 최소 (1 - 1/k)² · MDS(C) 크기의 분리 세트를 찾는다.^[10]

가장 작은 디스크의 직경이 1. 크기의 로그에 따라 디스크를 레벨로 분할하십시오.즉, j-th 레벨은 j ≤ 0(가장 작은 디스크가 레벨 0에 있음)^j+1에 대해 (k ^j+ 1) ~ (k + 1) 사이의 직경을 가진 모든 디스크를 포함한다.

각 수준 j에 대해 서로 떨어져 있는 선(^j+1k + 1)으로 구성된 평면에 그리드를 부과한다.시공에 의해, 모든 디스크는 그것의 레벨로부터 하나의 수평선과 하나의 수직선에서 교차할 수 있다.

0과 k 사이의 모든 r에 대해, 지수 modulo k가 r인 어떤 수평선이나 지수 modulu k가 s인 어떤 수직선과 교차하지 않는 디스크의 하위 집합으로 D(r,s)를 정의한다.By the pigeonhole principle, there is at least one pair (r,s) such that $\mathrm {MDS} (D(r,s)) \geq (1-{\frac {1}{k}})^{2}\cdot \mathrm {MDS}$ , i.e., we can find the MDS only in D(r,s) and miss only a small fraction of the disks in the optimal solution:

가능한 r,s(0 s r,s < k)의 모든 k 값에² 대해 동적 프로그래밍을 사용하여 D(r,s)를 계산한다.
이 k 세트² 중 가장 큰 세트를 반환하십시오.

버전 2

점 데이터가 있는 영역 사분면 트리

버전 2는 모든 상수 k > 1에 대해 시간 n에서^O(k) 최소 (1 - 2/k) 및 MDS(C) 크기의 분리 세트를 찾는다.^[5]

이 알고리즘은 시프트 쿼드트리를 사용한다.알고리즘의 핵심 개념은 쿼드트리 그리드에 대한 정렬이다.크기 r의 물체는 최대 kr(R kr kr) 크기의 쿼드트리 셀 안에 있으면 k- 정렬(여기서 k ≥ 1은 상수)이라고 한다.

정의상, 크기 R의 쿼트리 셀의 경계를 교차하는 k-정렬 물체는 적어도 R/k(r > R/k)의 크기를 가져야 한다.크기 R의 셀 경계는 크기 R/k의 4k 제곱으로 덮을 수 있다. 따라서 해당 셀의 경계와 교차하는 분리 지방 개체의 수는 최대 4kc로, 여기서 c는 대상의 비만도를 측정하는 상수다.

따라서 모든 물체가 지방과 k-정렬된 경우 분할-컨커머 알고리즘을 사용하여 시간 n으로^O(kc) 설정된 정확한 최대 분리 집합을 찾을 수 있다.모든 개체를 포함하는 쿼드트리 셀로 시작하십시오.그런 다음 이를 더 작은 4중 셀로 재귀적으로 나누고 각 작은 셀에서 최대값을 찾은 다음 결과를 결합하여 더 큰 셀에서 최대값을 얻으십시오.모든 쿼드트리 셀의 경계를 교차하는 분리 지방 물체의 수는 4kc로 제한되기 때문에, 우리는 어떤 물체가 최적의 용액에서 경계를 교차하는지 간단히 "가져보고" 그 안에 있는 물체에 분할과 결합을 적용할 수 있다.

거의 모든 물체가 k-정렬되어 있다면 k-정렬되지 않은 물체는 그냥 버리고, 나머지 물체의 최대 분리 집합을 시간^O(k) n으로 찾을 수 있다.이로 인해 (1 - e) 근사치가 발생하며, 여기서 e는 k-정렬되지 않은 물체의 일부분이다.

대부분의 물체가 k-정렬되지 않은 경우 (1/k,1/k)의 배수로 그리드를 이동하여 k-정렬되도록 할 수 있다.첫째, 모든 물체가 장치 사각형에 포함되도록 크기를 조정한다.그런 다음 그리드의 k 이동을 고려한다: (0,0), (1/k,1/k), (2/k, 2/k), ..., (k - 1)/k, (k - 1)/k, (k - 1)/k.즉, {0, ...,k - 1}의 각 j에 대해 (j/k,j/k)의 격자 이동을 고려한다.최소 k - 2의 j 값에 대해 모든 라벨이 2k 정렬됨을 증명할 수 있다.이제 모든 j에 대해 (j/k,j/k) 교대조에서 k-정렬되지 않은 객체를 버리고 나머지 객체의 최대 분리 집합을 찾으십시오.A(j) 집합으로 전화하십시오.실제 최대 연결 해제 세트는 A*이다.다음:

$\sum _{j=0,\ldots,k-1}{ A(j) }\geq(k-2) A*$

따라서 가장 큰 A(j)의 크기는 최소한 다음과 같다. (1 - 2/k) A*. 알고리즘의 반환값은 가장 큰 A(j)이며, 근사계수는 (1 - 2/k), 실행시간은 n이다^O(k).우리는 우리가 원하는 만큼 근사 인자를 작게 만들 수 있다. 그래서 이것은 PTAS이다.

두 버전 모두 d 치수(근사비가 다른 경우)와 가중 사례로 일반화할 수 있다.

기하 분리기 알고리즘

몇 가지 분할과 컨커머 알고리즘은 특정한 기하학적 구분자 정리에 기초한다.기하학적 분리기는 주어진 형상 집합을 두 개의 작은 부분 집합으로 구분하는 선이나 모양을 말하며, 분할 중 손실된 형상 수가 상대적으로 적다.이것은 아래에 설명된 대로 PTAS와 하위 성능의 정확한 알고리즘을 모두 허용한다.

임의 크기의 지방 객체: 기하학적 구분자를 사용한 PTAS

C는 임의 크기의 n개의 뚱뚱한 물체 집합이 되게 하라.다음 알고리즘은 모든 상수 b > 1에 대해 시간 n에서^O(b) 최소 (1 - O(√b) 및 MDS(C) 크기의 디스조인트 세트를 찾는다.^[5]

알고리즘은 다음과 같은 기하학적 분리기 정리를 바탕으로 하며, 이는 분리 사각형의 기하 분리기가 존재한다는 증거와 유사하게 증명될 수 있다.

지방 개체의 C 세트마다 C를 C_inside, C_outside, C, C의_boundary 세 하위 집합으로 분할하는 직사각형이 있다.

MDS(C_inside) ≤ MDS(C)
MDS(C_outside) ≤ MDS(C)
MDS(C_boundary) c√ MDS(C)

여기서 a와 c는 상수다.MDS(C)를 정확하게 계산할 수 있다면 분리기 사각형을 적절하게 선택하여 상수를 2/3까지 낮출 수 있다.그러나 MDS(C)를 상수 인자로만 추정할 수 있으므로 상수 a는 더 커야 한다.다행히도 a는 C로부터 계속 독립된 상태로 남아 있다.

이 분리 정리에서는 다음과 같은 PTAS를 구축할 수 있다.

상수 b를 선택하십시오.최대 b + 1 라벨의 가능한 모든 조합을 확인하십시오.

MDS(C)의 크기가 최대 b(즉, 모든 b + 1 라벨 세트가 분리되지 않음)인 경우 해당 MDS를 반환하고 종료하십시오.이 단계에는 시간이^O(b) 걸리지 않는다.
그렇지 않으면 기하학적 구분 기호를 사용하여 C를 두 하위 집합으로 구분하십시오.C와_inside C에서_outside MDS의 근사치를 각각 찾아내고, C에서 MDS의 근사치로 이들의 조합을 반환한다.

최적의 MDS 크기가 MDS(C) = m일 때 E(m)를 위 알고리즘의 오류로 한다. m ≤ b일 때, 최대 분리 세트가 정확히 계산되기 때문에 오류가 0이며, m > b일 때, 오차는 최대 c√m까지 분리기와 교차하는 라벨의 수가 증가한다.알고리즘의 최악의 경우는 각 단계의 분할이 가능한 최대 비율인 a(1 - a)에 있는 경우다.따라서 오류 함수는 다음과 같은 반복 관계를 만족한다.

E(m)=0\ \\ \ \\text{{{}m\leq b

E(m)=E(a\cdot m)+E(1-a)\cdot m)+c\cdot {\sqrt{{}{{}m>b

이러한 재발에 대한 해결책은 다음과 같다.

E(m)=({\frac {0}{b}}+{\frac {c}{{\sqrt {b}}({\sqrt {a}}+{\sqrt {1-a}}-1)}})\cdot m-{\frac {c}{{\sqrt {a}}+{\sqrt {1-a}}-1}}\cdot {\sqrt {m}}.

예: $E(m)=O(m/{\sqrt {b}})$ ( $E(m)=O(m/{\sqrt {b}})$ ) $E(m)=O(m/{\sqrt {b}})$ = $E(m)=O(m/{\sqrt {b}})$ ( $E(m)=O(m/{\sqrt {b}})$ / b $){\displaystyle E(m)=O(m/{\sqrt{b$ b를 적절히 선택하면 근사계수를 원하는 만큼 작게 만들 수 있다.

이 PTAS는 사분면에 기초한 PTAS보다 공간 효율적이며, 물체가 미끄러질 수 있는 일반화를 처리할 수 있지만 가중 케이스를 처리할 수 없다.

경계 크기 비율(bound size-ratio): 정확한 하위 확장 알고리즘이 있는 디스크

가장 큰 반지름과 가장 작은 반지름 사이의 비율이 최대 r이 되도록 C를 n개의 디스크 집합으로 한다.다음 알고리즘은 정확히 시간 $2^{O(r\cdot {\sqrt {n}})}$ O $2^{O(r\cdot {\sqrt {n}})}$ ( r $2^{O(r\cdot {\sqrt {n}})}$ $){\$ 의 MDS(C)를 찾아낸다 $2^{O(r\cdot {\sqrt {n}})}$ ^[11]

알고리즘은 C에 있는 모든 디스크의 중심에 대해 설정된 Q에 폭 경계 기하학적 분리기를 기반으로 한다.이 분리 정리에서는 다음과 같은 정확한 알고리즘을 구축할 수 있다.

분리기 선을 찾아 2n/3 중심은 오른쪽(C_right), 2n/3 중심은 왼쪽(C_left), O(O) 중심은 선(C_int)에서 r/2 미만 거리에 있도록 한다.
모든_int 가능한 오버랩되지 않는 C 하위 세트를 고려하십시오.최대 $2^{O(r\cdot {\sqrt {n}})}$ $){\$ 2 $^{O(r\cdot{\sqrt{n}}})}}}}}}}$ 그러한 $2^{O(r\cdot {\sqrt {n}})}$ 하위 집합이 있다.그러한 각 부분 집합에 대해 C의_left MDS와 C의_right MDS를 재귀적으로 계산하고, 가장 큰 조합 세트를 반환한다.

이 알고리즘의 실행 시간은 다음과 같은 반복 관계를 만족한다.

T(1)=1

T(n)=2^{O(r\cdot {\sqrt{n}})}T\left({\frac {2n}{3}\오른쪽){\text{{}}{{}n>1

이러한 재발에 대한 해결책은 다음과 같다.

T(n)=2^{O(r\cdot {\sqrt{n}})}}}

로컬 검색 알고리즘

유사 디스크: PTAS

사이비 디스크 집합은 모든 개체 쌍의 경계가 최대 두 번 교차하는 개체 집합이다.(이 정의는 전체 컬렉션과 관련되며 컬렉션에 포함된 특정 개체의 모양에 대해서는 아무 말도 하지 않는다는 점에 유의하십시오.사이비 디스크 집합은 경계 조합 복잡성을 가지고 있다. 즉, 모든 객체의 결합 경계에 있는 교차점 수가 객체 수로 선형이다.

C는 n개의 객체를 가진 유사 디스크 집합이 되게 하라.The following local search algorithm finds a disjoint set of size at least $(1-O({\frac {1}{\sqrt {b}}}))\cdot MDS(C)$ in time $O(n^{b+3})$ , for every integer constant $b\geq 0$ :^[12]

초기화: $빈$ 세트 S $S$ 초기화 $S$
검색: $C-S$ 가 $C-S$ 1과 $b+1$ + $b+1$ C $C-S$ - $C-S$ ${\$ $displaystyle C-S}$ 의 모든 하위 세트를 반복하십시오 $b+1$ 이러한 각 부분 집합 X에 대해:
- X 자체가 독립적인지 확인하십시오(그렇지 않으면 다음 하위 집합으로 이동).
- X를 교차하는 S에 있는 객체의 Y 설정값을 계산한다.
- $|Y|<|X|$ < $|Y|<|X|$ $displaystyle$ Y < X $|Y|<|X|$ 인 경우 S에서 Y를 제거하고 X: $S:=S-Y+X$ $S:=S-Y+X$ $S:=S-Y+X$ - $S:=S-Y+X$ + $S:=S-Y+X$ ${\displaystyle$ S $:=S-Y+X}$ 를 삽입하십시오 $S:=S-Y+X$
끝: 세트 S를 반환하십시오.

검색 단계에서 교환할 때마다 S의 크기가 최소 1씩 증가하므로 최대 n번까지 발생할 수 있다.

알고리즘은 매우 간단하다. 어려운 부분은 근사 비율을 증명하는 것이다.^[12]

참고 항목.^[13]

선형 프로그래밍 완화 알고리즘

유사 디스크: PTAS

C는 n개의 객체와 조합 복잡성을 가진 사이비-디스크 세트가 되게 하라.Using linear programming relaxation, it is possible to find a disjoint set of size at least ${\frac {n}{u}}\cdot MDS(C)$ . This is possible either with a randomized algorithm that has a high probability of success and run time $O(n^{3})$ , or a deterministic al런타임은 느리지만 다항식인 고리템.이 알고리즘은 가중 사례로 일반화할 수 있다.^[12]

근사치를 알 수 있는 기타 유형의 모양

2차원 평면의 선 세그먼트.^[13]^[14]
임의의 2차원 볼록한 물체.^[13]
경계 교차점 수가 있는 곡선.^[14]

외부 링크

유사 디스크의 최대 독립 집합에 대한 근사 알고리즘 - Sariel Har-Feled에 의한 표시.
정확한 최대 직사각형 분리 집합을 계산하기 위한 자바스크립트 코드.

메모들

^ 라비, S.S., 헌트, H.B(1987년)."는 평면 분리 정리의 문제들은 개표장 응용 프로그램".정보 처리 불능. 25(5):317.doi:10.1016(87)90206-7. 스미스, W.D.;워멀드, N.C.(1998년)."기하학적 구분 정리 그리고 응용 프로그램".컴퓨터 과학(고양이의 기초에 논문집 제39회 심포지엄.No.98CB36280)p. 232번이에요. doi:10.1109/sfcs.1998.743449.아이 에스비엔 978-0-8186-9172-0.S2CID 17962961.
^ ^a ^b ^c ^d Agarwal, P. K.; Van Kreveld, M.; Suri, S. (1998). "Label placement by maximum independent set in rectangles". Computational Geometry. 11 (3–4): 209. doi:10.1016/s0925-7721(98)00028-5. hdl:1874/18908.
^ ^a ^b Marathe, M. V.; Breu, H.; Hunt, H. B.; Ravi, S. S.; Rosenkrantz, D. J. (1995). "Simple heuristics for unit disk graphs". Networks. 25 (2): 59. arXiv:math/9409226. doi:10.1002/net.3230250205.
^ ^a ^b Hochbaum, D. S.; Maass, W. (1985). "Approximation schemes for covering and packing problems in image processing and VLSI". Journal of the ACM. 32: 130–136. doi:10.1145/2455.214106. S2CID 2383627.
^ ^a ^b ^c Chan, T. M. (2003). "Polynomial-time approximation schemes for packing and piercing fat objects". Journal of Algorithms. 46 (2): 178–189. CiteSeerX 10.1.1.21.5344. doi:10.1016/s0196-6774(02)00294-8.
^ Chalermsook, P.; Chuzhoy, J. (2009). "Maximum Independent Set of Rectangles". Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms. p. 892. doi:10.1137/1.9781611973068.97. ISBN 978-0-89871-680-1.
^ Chalermsook, P. (2011). "Coloring and Maximum Independent Set of Rectangles". Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. Lecture Notes in Computer Science. Vol. 6845. pp. 123–134. doi:10.1007/978-3-642-22935-0_11. ISBN 978-3-642-22934-3.
^ Abed, Fidaa; Chalermsook, Parinya; Correa, José; Karrenbauer, Andreas; Pérez-Lantero, Pablo; Soto, José A.; Wiese, Andreas (2015). On Guillotine Cutting Sequences. pp. 1–19. doi:10.4230/LIPIcs.APPROX-RANDOM.2015.1. ISBN 978-3-939897-89-7.
^ Mitchell, Joseph S. B. (2021-06-25). "Approximating Maximum Independent Set for Rectangles in the Plane". arXiv:2101.00326 [cs.CG].
^ Erlebach, T.; Jansen, K.; Seidel, E. (2005). "Polynomial-Time Approximation Schemes for Geometric Intersection Graphs". SIAM Journal on Computing. 34 (6): 1302. doi:10.1137/s0097539702402676.
^ Fu, B. (2011). "Theory and application of width bounded geometric separators". Journal of Computer and System Sciences. 77 (2): 379–392. doi:10.1016/j.jcss.2010.05.003.
^ ^a ^b ^c Chan, T. M.; Har-Peled, S. (2012). "Approximation Algorithms for Maximum Independent Set of Pseudo-Disks". Discrete & Computational Geometry. 48 (2): 373. arXiv:1103.1431. doi:10.1007/s00454-012-9417-5. S2CID 38183751.
^ ^a ^b ^c Agarwal, P. K.; Mustafa, N. H. (2006). "Independent set of intersection graphs of convex objects in 2D". Computational Geometry. 34 (2): 83. doi:10.1016/j.comgeo.2005.12.001.
^ ^a ^b Fox, J.; Pach, J. N. (2011). "Computing the Independence Number of Intersection Graphs". Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms. p. 1161. CiteSeerX 10.1.1.700.4445. doi:10.1137/1.9781611973082.87. ISBN 978-0-89871-993-2. S2CID 15850862.

[1] 라비, S.S., 헌트, H.B(1987년)."는 평면 분리 정리의 문제들은 개표장 응용 프로그램".정보 처리 불능. 25(5):317.doi:10.1016(87)90206-7. 스미스, W.D.;워멀드, N.C.(1998년)."기하학적 구분 정리 그리고 응용 프로그램".컴퓨터 과학(고양이의 기초에 논문집 제39회 심포지엄.No.98CB36280)p. 232번이에요. doi:10.1109/sfcs.1998.743449.아이 에스비엔 978-0-8186-9172-0.S2CID 17962961.

[Agarwal1998-2] Agarwal, P. K.; Van Kreveld, M.; Suri, S. (1998). "Label placement by maximum independent set in rectangles". Computational Geometry. 11 (3–4): 209. doi:10.1016/s0925-7721(98)00028-5. hdl:1874/18908.

[Marathe1995-3] Marathe, M. V.; Breu, H.; Hunt, H. B.; Ravi, S. S.; Rosenkrantz, D. J. (1995). "Simple heuristics for unit disk graphs". Networks. 25 (2): 59. arXiv:math/9409226. doi:10.1002/net.3230250205.

[HochbaumMaass1985-4] Hochbaum, D. S.; Maass, W. (1985). "Approximation schemes for covering and packing problems in image processing and VLSI". Journal of the ACM. 32: 130–136. doi:10.1145/2455.214106. S2CID 2383627.

[Chan2003-5] Chan, T. M. (2003). "Polynomial-time approximation schemes for packing and piercing fat objects". Journal of Algorithms. 46 (2): 178–189. CiteSeerX 10.1.1.21.5344. doi:10.1016/s0196-6774(02)00294-8.

[6] Chalermsook, P.; Chuzhoy, J. (2009). "Maximum Independent Set of Rectangles". Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms. p. 892. doi:10.1137/1.9781611973068.97. ISBN 978-0-89871-680-1.

[7] Chalermsook, P. (2011). "Coloring and Maximum Independent Set of Rectangles". Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. Lecture Notes in Computer Science. Vol. 6845. pp. 123–134. doi:10.1007/978-3-642-22935-0_11. ISBN 978-3-642-22934-3.

[8] Abed, Fidaa; Chalermsook, Parinya; Correa, José; Karrenbauer, Andreas; Pérez-Lantero, Pablo; Soto, José A.; Wiese, Andreas (2015). On Guillotine Cutting Sequences. pp. 1–19. doi:10.4230/LIPIcs.APPROX-RANDOM.2015.1. ISBN 978-3-939897-89-7.

[9] Mitchell, Joseph S. B. (2021-06-25). "Approximating Maximum Independent Set for Rectangles in the Plane". arXiv:2101.00326 [cs.CG].

[Erlebach2005-10] Erlebach, T.; Jansen, K.; Seidel, E. (2005). "Polynomial-Time Approximation Schemes for Geometric Intersection Graphs". SIAM Journal on Computing. 34 (6): 1302. doi:10.1137/s0097539702402676.

[Fu-11] Fu, B. (2011). "Theory and application of width bounded geometric separators". Journal of Computer and System Sciences. 77 (2): 379–392. doi:10.1016/j.jcss.2010.05.003.

[ChanHarPeled2012-12] Chan, T. M.; Har-Peled, S. (2012). "Approximation Algorithms for Maximum Independent Set of Pseudo-Disks". Discrete & Computational Geometry. 48 (2): 373. arXiv:1103.1431. doi:10.1007/s00454-012-9417-5. S2CID 38183751.

[am06-13] Agarwal, P. K.; Mustafa, N. H. (2006). "Independent set of intersection graphs of convex objects in 2D". Computational Geometry. 34 (2): 83. doi:10.1016/j.comgeo.2005.12.001.

[fp11-14] Fox, J.; Pach, J. N. (2011). "Computing the Independence Number of Intersection Graphs". Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms. p. 1161. CiteSeerX 10.1.1.700.4445. doi:10.1137/1.9781611973082.87. ISBN 978-0-89871-993-2. S2CID 15850862.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

Search

최대 분리 세트

네임스페이스

더

목차

탐욕 알고리즘

1차원 구간: 정확한 다항식 알고리즘

지방 모양: 일정한 요인 근사치

분할 및 재무 알고리즘

높이가 같은 축-병렬 직사각형: 2-근

높이가 같은 축 평행 직사각형: PTAS

축-병렬 직사각형: 로그-인자 근사

축-병렬 직사각형: 상수 요인 근사

크기가 동일한 뚱뚱한 물체: PTAS

임의 크기의 뚱뚱한 개체: PTAS

버전 1

버전 2

기하 분리기 알고리즘

임의 크기의 지방 객체: 기하학적 구분자를 사용한 PTAS

경계 크기 비율(bound size-ratio): 정확한 하위 확장 알고리즘이 있는 디스크

로컬 검색 알고리즘

유사 디스크: PTAS

선형 프로그래밍 완화 알고리즘

유사 디스크: PTAS

근사치를 알 수 있는 기타 유형의 모양

외부 링크

메모들