기하분리기

기하학적 분리기는 기하학적 도형의 집합을 두 개의 부분 집합으로 분할하는 선(또는 다른 도형)으로, 각 부분 집합의 도형의 비율이 경계를 이루며, 어떤 부분 집합에 속하지 않는 도형의 수(즉, 분리자 자체와 교차하는 도형)가 작다.

기하학적 분리기가 존재할 때, 그것은 컴퓨터 기하학의 다양한 문제를 해결하기 위한 분할과 커커 알고리즘을 구축하는 데 사용될 수 있다.

선인 구분 기호

일반질문

1979년 헬지 트버버그는^[1] 다음과 같은 문제를 제기했다.두 개의 양의 정수 k, l에 대해, 가장 작은 n(k,l)은 무엇이며, 따라서 평면에 있는 쌍으로 분리된 볼록한 물체의 모든 계열에 대해, 한 면에는 적어도 k개의 물체가 있고 다른 면에는 적어도 l개의 물체가 있는 직선이 있는가?

다음과 같은 결과가 알려져 있다.

• 분명히 n(1,1)=1이다.
• 호프와 카찰스키는^[2] 모든 k ≥ 2에 대해 n(k,1) ≤ 12(k-1)임을 증명했다.
• 빌랑어는^[1] n(2,2) = ∞: 직선이 양쪽에 두 개의 세그먼트를 가지지 않을 정도로 쌍분할 세그먼트의 무한 패밀리를 보여주었다는 것을 증명했다.Pach and Tardos는^[3] 유닛 세그먼트만 사용하는 더 간단한 구조와 디스크(또는 사각형)만 사용하는 또 다른 구조를 보여주었다.

축-병렬 직사각형 분리기

평면 내 N=4k 분리 축-병렬 직사각형 집합에 대해 최소한 N/4 직사각형이 그 각 면에 완전히 놓여 있는 수평 또는 수직 직선이 있다(대부분의 N/2 직사각형은 분리선과 교차한다).

증명

W를 N/4 직사각형이 전체적으로 서쪽에 있는 가장 서쪽 수직선으로 정의하십시오.두 가지 경우가 있다.

• W의 동쪽에 최소한 N/4 직사각형이 있는 경우 W는 수직 분리막이다.
• 그렇지 않으면 W를 약간 서쪽으로 이동시킴으로써 N/2 직사각형보다 더 많이 교차하는 수직선을 얻게 된다.이 선에서 직사각형 위에 최소 N/4 직사각형이 있고 그 아래에 N/4 직사각형이 있는 점을 찾아 수평 분리기를 그린다.

최적성

위의 정리에 의해 보장된 교차형상의 수는 O(N)이다.이 상한은 오른쪽 그림에서와 같이 모양이 정사각형인 경우에도 점증적으로 단단하다.이는 분리기가 닫힌 형상일 때 보장되는 O(nN) 교차 형상 상단과 극명한 대조를 이룬다(이전 섹션 참조).

더욱이 형상이 임의의 직사각형일 경우 오른쪽 그림에서와 같이 하나의 직사각형 이상을 구분하는 선은 N/4 직사각형 이하로 교차할 수 없는 경우가 있다.^[4]

일반화

위의 정리는 분리 직사각형에서 k-thick 직사각형까지 일반화할 수 있다.또한 d에 대한 유도에 의해 d차원에 대한 위의 정리를 일반화하여 다음과 같은 정리를 얻을 수 있다.^[5]

내부 내부가 k-thick인 N축 평행 d-box에 주어진 경우, 최소한 다음과 같은 축 평행 하이퍼 평면이 존재한다.

${\displaystyle \lfloor (N+1-k)/(2d)\rfloor }$

D-box 인테리어의 각 측면에 위치한다.

k = N - 1(즉, 각 점이 최대 N - 1 박스에 포함되어 있는 경우)의 특별한 경우, 다음과 같은 정리가 유지된다.^[5]

내부가 (N - 1)-thick인 N축 평행 d-box에 주어진 경우, 두 개의 내부를 분리하는 축 평행 하이퍼플레인이 존재한다.

물체는 상자가 될 필요가 없으며, 분리자는 축 평행일 필요가 없다.

C를 하이퍼플레인의 가능한 방향(예: C = {수평, 수직})의 집합으로 한다.N d-객체(각각 두 개의 분리된 물체가 내부가 k-thick인 C의 방향을 가진 하이퍼플레인에 의해 분리되는 경우)에 따라, 최소한 d-객체 내부의 (N + 1 - k)/O(C)가 하이퍼플레인의 양쪽에 완전히 놓여 있는 하이퍼플레인이 존재한다.

알고리즘 버전

O(Nd) 단계에서 위의 이론에 의해 보장된 하이퍼플레인을 찾을 수 있다.또한, 상자의 ith 좌표를 정의하는 구간의 하단 끝점과 상단 끝점의 2d 목록을 사전 정렬할 경우, O(Nd) 단계에서 (다양한 최적성 측정에 따라) 그러한 하이퍼플레인 중에서 가장 우수한 것을 찾을 수 있다.

닫힌 형상인 구분 기호

구분자가 존재한다고 보장되는 간단한 경우는 다음과 같다.^[5][6]

평면에 n개의 이음매-병행 제곱 세트를 주어, 사각형의 2n/3이 R 안에 있고, 2n/3이 R 밖에 있고, 대부분의 사각형의 O(sqrt(n)가 R 안에 있지 않고 R의 경계를 교차하지 않는 직사각형 R이 있다.

따라서 R은 n 제곱을 두 개의 부분 집합("R 내부"와 "외부 R")으로 구분하는 기하학적 구분자(R과 교차하는 제곱은 두 하위 집합 중 어느 하나에 속하지 않기 때문에 "잃어버린" 것으로 간주된다.

증명

2-지방 직사각형을 최대 2의 가로 세로 비율을 가진 축 평행 직사각형으로 정의하십시오.

R은₀ 최소한 n/3 사각형의 중심을 포함하는 최소 면적 2-지방 직사각형이 되도록 한다.따라서 R보다₀ 작은 모든 2-지방 직사각형은 n/3 제곱 미만을 포함한다.

[0,1]의 모든 t에 대해 R은_t 1 + t만큼 팽창된 R과₀ 같은 중심을 가진 2-지방 직사각형이 되도록 한다.

• R은_t R을₀ 포함하므로 최소 n/3 제곱의 중심을 포함한다.
• R은_t R보다₀ 2배 이하 크기여서 R보다₀ 작은 2-지방 직사각형 2개로 덮을 수 있다.이 2-지방 직사각형들은 각각 n/3 제곱 이하의 중심을 포함하고 있다.따라서 R은_t 2n/3제곱 이하의 중심을 포함한다.

이제 대부분의 O(sqrt(n) 제곱에서 R이_t 교차하는 t가 있다는 것을 보여주기 위해 남아 있다.

그래서 가장 12n{\displaystyle 12{\sqrt{n}에서}교차할 수 있는 첫째, 정사각형 –의 side-length은 최소 폭 ⁡(미국의 0)/2n{\displaystyle \operatorname{너비}(R_{0}){\sqrt{n}}}. 모든 t 들어, 그러나 주변 대부분의 2·perimeter(R0)은 기껏 6·width(R0)을 느끼고 있다면,}모든" 큰 칸"을 고려해 l.아그정사각형

다음으로, 모든 "작은 사각형" – 측면 길이가 ${\displaystyle \mathrm{너비}}$ ${\displaystyle }$ ${\displaystyle ({}_{}}$ ${\displaystyle {0\mathrm{}}_{}}$)${\displaystyle }$/ ${\displaystyle 2n\sqrt{}}$ ${\$보다 작은 사각형을 고려하십시오$.$

모든 t에 대해: R의_t 경계와 교차하는 작은 사각형 집합으로 교차(t)를 정의한다.모든 t1과 t2,1− t2≥ t1/n{\displaystyle t_{1}-t_{2}\geq 1{\sqrt{n}}}, 너비 ⁡(Rt 1)− 폭 ⁡(Rt 2)≥ 폭 ⁡ 들어(미국의 0)/n{\displaystyle \operatorname{너비}(R_{t_{1}})-\operatorname{폭}(R_{t_{2}})\geq\operatorname{폭}(R_{0})/{\sqr.t$\{$$n}}.$따라서 R의_t1 경계와 R의_t2 경계 사이에는$$ ${\displaystyle \mathrm{최소}}$ 폭${\displaystyle }$⁡ ${\displaystyle ({R\mathrm{}}_{}}$ 0${\displaystyle {}_{}}$)${\displaystyle }$/ ${\displaystyle 2n\sqrt{}}$ ${\$의 간격이 있다.따라서 교차(t₁)와 교차(t₂)는 분리된다.따라서 다음과 같다.

${\displaystyle \sum _{j=0}^{\sqrt{n1}-1}{\sqrt {n}{\sqrt{n}}}{\leqn}}$

그러므로 비둘기 구멍 원리에 의해 다음과 같은 특정한 j가₀ 있다.

${\displaystyle \propertname {n}(j_{0}/{\sqrt{n}}) \leq {\sqrt{n}}}$

우리가 찾는 구분자는 직사각형 R인데_t 여기서 $t{\displaystyle }$= ${\displaystyle {j\mathrm{}}_{}}$ ${\displaystyle 0\sqrt{}{}_{}}$/ n ${\$^[7]

적용 예

이 분리막 정리를 이용하여 다음과 같은 방법으로 계산 기하학의 어떤 문제를 해결할 수 있다.

• 입력 제곱 세트를 두 개의 분리 하위 세트로 분리한다.
• 각 하위 집합의 문제를 개별적으로 해결하십시오.
• 두 개의 하위 문제에 해결책을 결합하고 원래 문제에 대한 대략적인 해결책을 구하라.

일반화

위의 정리는 여러 가지 방법으로 일반화할 수 있으며, 상수도 다를 수 있다.예를 들면 다음과 같다.

• 입력 컬렉션은 사각형 대신 원, 경계 종횡비가 있는 직사각형 등 임의의 지방 개체를 포함할 수 있다.
• 평면 내 2차원 형상 대신 입력 컬렉션은 어떤 차원의 물체를 포함할 수 있으며, d차원 토러스(torus)에 위치할 수 있다.
• 입력 컬렉션의 형상을 분리하도록 요구하는 대신,^[5] 수집이 다음과 같은 더 약한 요구 사항을 제시할 수 있다.
  • k-16, 즉, 각 점은 최대 k k개의 다른 모양에 의해 가려진다.
  • l-k-migration, 즉, 각 점은 크기 비율(가장 큰 모양의 크기를 가장 작은 모양의 크기로 나눈 값)을 가진 최대 k개의 다른 모양에 의해 덮인다.
  • k-눈금, 즉, 도형의 하위 집합에 대해 개별 측정치의 합은 최대 k배 조합의 측정값이다.
• 직사각형 분리기 대신에 분리기는 그 자체의 더 작은 복사본으로 덮을 수 있는 어떤 형태도 될 수 있다.
• 분리기 각 면의 형상 수를 경계하는 대신 특정 공리를 만족시키는 척도를 경계하는 것이 가능하다.^[6]

최적성

위의 정사각형 분리막 정리에서는 1:2의 비율이 가장 잘 보장된다: O(sqrt(n) 모양만 교차하는 분리막을 사용하여 더 나은 비율로 분리할 수 없는 형상 모음이 있다.다음과 같은 수집이 있다(의 정리 34로부터).

정삼각형을 생각해봐.그것의 3개의 꼭지점에서, 지름이 나선형의 회전마다 일정한 인수로 증가하도록 지수 나선형으로 배열된 N/3 형상을 넣고, 각 형상은 나선형 순서에서 그 이웃에 닿도록 한다.예를 들어, 1-By-RW 직사각형으로 시작하십시오. 여기서 φ은 황금 비율입니다.인접한 φ별 제곱을 추가하고 또 다른 황금 직사각형을 얻으십시오.인접한(1+RW) 기준(1+RW) 사각형을 추가하고 더 큰 금색 직사각형 등을 구한다.

이제 형상의 1/3 이상을 분리하기 위해서는 분리기가 O(N) 형상을 두 개의 서로 다른 꼭지점에서 분리해야 한다.그러나 이를 위해 분리기는 O(N) 모양을 교차해야 한다.

병렬 하이퍼플레인 사이의 너비 경계 스트립인 구분자

^[8]

Q는 점 사이의 최소 거리가 d가 되도록 평면에서 n개의 점 집합으로 한다.a>>0을 상수가 되게 하라.

거리 a의 한 쌍의 평행선이 있어, 최대 2n/3 지점이 스트립의 양쪽에 놓여 있고, 최대 $1{\displaystyle .3}$ ${\displaystyle \frac{a}{}}$ ${\displaystyle d\sqrt{}}$ ${\$ 지점이$$ 스트립 내부에 놓여 있다.

동등하게: 최대 2n/3 포인트는 양쪽에, 최대 $1{\displaystyle .3}$ ${\displaystyle \frac{a}{}}$ ${\displaystyle d\sqrt{}}$ ${\$ 1$.3{a \over d}{\sqrt{n}}}$ 포인트는$$ 그것으로부터 1/2 미만의 거리에 놓여 있는 선이 있다.

교정 스케치

Q의 중심점을 포인트 o로 정의하여 이를 통과하는 모든 라인의 각 면에 최대 2n/3의 Q 포인트가 되도록 한다.중심점의 존재는 헬리의 정리를 이용하여 증명할 수 있다.

주어진 점 p와 상수 a>0에 대해, o를 통과하는 임의의 선이 p에서 a 이하의 거리에 위치할 확률로 Pr(a,p,o)를 정의한다.아이디어는 이러한 확률을 구속하고 따라서 무작위 선에서 o까지 a보다 작은 거리에서 점의 예상 개수를 구속하는 것이다.그렇다면, 비둘기 구멍 원리에 의해 적어도 하나의 o선을 통과하는 것이 원하는 구분선이다.

적용들

경계 폭 분리기는 단백질 접힘 문제를 대략적으로 해결하는 데 사용될 수 있다.^[9]또한 기하학적 그래프에서 최대 독립적 집합과 관련된 몇 가지 포함 문제를 찾는 데 정확한 하위 알고리즘에도 사용할 수 있다.^[8]

기하학적 구분자 및 평면 그래프 구분자

평면 분리막 정리는 평면 내 디스크 시스템의 접촉 그래프로 평면 그래프를 나타내는 원 패킹 정리를 사용한 다음, 그러한 디스크에 대한 기하학적 분리막을 형성하는 원을 발견함으로써 증명될 수 있다.^[10]

참고 항목

• 햄 샌드위치 정리: n차원 공간에서 측정 가능한 물체가 없는 경우, 하나의 (n - 1)차원 하이퍼플레인으로 모든 물체를 (그들의 측정, 즉 부피와 관련하여) 반으로 나눌 수 있다.
• 기요틴 분리: 기요틴 절단기를 이용해 비행기에서 볼록한 물체를 분리하는 문제.
• 기타 분리 정리.
• 동시 구분자: 각 집합의 작은 수의 도형을 동시에 교차시키면서 여러 집합의 도형을 동시에 구분하는 구분자가 항상 존재하는 것은 아닐 수 있다.^[11]

메모들