벤틀리-오트만 알고리즘

컴퓨터 기하학에서 Bentley-Otmann 알고리즘은 일련의 선 세그먼트에서 모든 교차를 나열하기 위한 스위프 라인 알고리즘이다. 즉, 선 세그먼트의 교차로점(또는 단순하게 교차점)을 찾는다. 샤모스를 확장한다.Hoey 알고리즘,^[1] 선 세그먼트 집합에 교차가 있는지 여부를 테스트하기 위한 유사한 이전 알고리즘. For an input consisting of ${\displaystyle n}$ line segments with ${\displaystyle k}$ crossings (or intersections), the Bentley–Ottmann algorithm takes time ${\displaystyle {\mathcal {O}}((n+k)\log n)}$. In cases where ${\displaystyle k={\mathcal {o}}\left$$({\frac{n^{2}}:{\log n}\오른쪽$ 이것은 모든 세그먼트 쌍을 테스트하는 순진한 알고리즘의 개선으로, $\theta {\displaystyle \mathrm{}}$(${\displaystyle {n\mathrm{}}^{}}$ 2$){\displaystyle \Theta (n^{$2})가 소요된다$.$

이 알고리즘은 처음에 존 벤틀리와 토마스 오트만(1979)에 의해 개발되었다. 이 알고리즘은 교과서인 프리바타 & 샤모스(1985), 오로르케(1998), 드 버그 외 알에 더 자세히 설명되어 있다. (2000). 지금은 샤젤 앤 에델스브루너(1992년)와 발라반(1995년)에 의해 무증상적으로 더 빠른 알고리즘이 알려져 있지만, 벤틀리-오트만 알고리즘은 단순성과 낮은 메모리 요구^{[citation needed]} 사항 때문에 실용적인 선택으로 남아 있다.

종합전략

벤틀리-오트만 알고리즘의 주요 아이디어는 수직선 L이 평면을 가로질러 왼쪽에서 오른쪽으로(또는 위에서 아래로) 이동하는 스위프 라인 접근법을 사용하는 것으로, 이동하면서 입력선 세그먼트를 순서대로 교차한다.^[2] 알고리즘은 일반 위치에서 가장 쉽게 설명되며, 그 의미는 다음과 같다.

1. 두 개의 선 세그먼트 끝점 또는 교차점이 동일한 x 좌표를 가지지 않음
2. 다른 선 세그먼트에 선 세그먼트 끝점이 없음
3. 한 점에서 교차하는 세 개의 선 세그먼트는 없다.

그러한 경우 L은 항상 유한한 이산형 사건 집합에서만 수직 순서가 변하는 점 집합에서 입력선 세그먼트를 교차한다. 특히 이산형 이벤트는 선분할의 끝점(왼쪽 또는 오른쪽) 또는 두 선분할의 교차점과 연관될 수 있다. 따라서 L의 연속적인 운동은 스텝의 유한한 순서로 분해될 수 있으며, 유한한 시간 동안 실행되는 알고리즘에 의해 시뮬레이션될 수 있다.

이 시뮬레이션 과정 중에 발생할 수 있는 두 가지 유형의 이벤트가 있다. L이 선 세그먼트 s의 끝점을 스윕할 때, s와 L의 교차점은 수직으로 정렬된 교차점 집합에 추가되거나 제거된다. 이러한 이벤트는 엔드포인트가 입력부터 알고리즘까지 이미 알려져 있기 때문에 예측하기 쉽다. 나머지 이벤트는 L이 두 선 세그먼트 s와 t 사이의 교차(또는 교차점)를 가로질러 스위프할 때 발생한다. 이러한 이벤트는 이벤트 직전에 L과 s, t의 교차점이 교차점의^{[clarification needed]} 수직 순서에 인접해 있다는 사실에서도 예측할 수 있다.

Bentley-Otmann 알고리즘 자체는 입력 라인 세그먼트와 스위프 라인의 교차점 및 인접 교차점 쌍에 의해 형성된 잠재적 미래 사건의 집합의 현재 수직 순서를 나타내는 데이터 구조를 유지한다. 그것은 새로운 교차점 집합을 나타내기 위해 데이터 구조를 업데이트하면서 각 이벤트를 차례로 처리한다.

데이터 구조

이 섹션은 독자들에게 혼란스럽거나 불명확할 수 있다. 특히 바이너리 검색 트리의 내부 및 리프 노드가 나타내는 것은 설명되지 않는다. 라인 세그먼트의 이전 또는 후속 요소를 삽입, 삭제 또는 찾으면서 라인 세그먼트는 서로 어떻게 비교되고 있는가? 무엇이 라인 세그먼트를 다른 라인 세그먼트의 선행 및 후속으로 만드는가? 섹션을 명확히 설명하는 데 도움을 주십시요. 토크 페이지에서 이에 대한 논의가 있을 수 있다(2018년 3월) (이 템플릿 메시지를 제거하는 방법과 시기 알아보기)

스위프 라인 L의 교차점과 입력 라인 세그먼트 및 미래 이벤트 시퀀스를 효율적으로 유지하기 위해 Bentley-Otmann 알고리즘은 다음과 같은 두 가지 데이터 구조를 유지한다.

• L을 가로지르는 입력 라인 세그먼트 집합을 포함하는 이진 검색 트리("스위프 라인 상태 트리")로, 이러한 세그먼트가 L을 가로지르는 지점의 y 좌표로 정렬된다. 교차점 자체는 바이너리 검색 트리에 명시적으로 표시되지 않는다. Bentley-Otmann 알고리즘은 스위프 라인 L이 이 세그먼트의 왼쪽 끝점 p(즉, 이 문서에서 설명한 대로 스위프 라인 L이 왼쪽에서 시작된다면 가장 작은 x 좌표를 가진 세그먼트의 끝점)를 통과할 때 이 데이터 구조에 새로운 세그먼트 s를 삽입한다. 이진 검색 트리에서 세그먼트 s의 정확한 위치는 이진 검색에 의해 결정될 수 있으며, 이 검색의 각 단계는 p가 L에 의해 교차되는 일부 다른 세그먼트의 위 또는 아래에 있는지 여부를 테스트한다. 따라서 로그 시간에 삽입을 수행할 수 있다. 또한 Bentley-Otmann 알고리즘은 바이너리 검색 트리에서 세그먼트를 삭제하고, 바이너리 검색 트리를 사용하여 다른 세그먼트 바로 위나 아래에 있는 세그먼트를 결정한다. 이러한 연산은 세그먼트의 기본 기하학적 구조를 참조하지 않고 트리 구조 자체만을 사용하여 수행할 수 있다.

• Bentley-Otmann 알고리즘의 잠재적 미래 이벤트 순서를 유지하는 데 사용되는 우선 순위 대기열("이벤트 대기열") 각 이벤트는 세그먼트 끝점 또는 교차점, 평면의 점 p와 연관되며, 이벤트는 L선이 p를 스윕할 때 발생한다. 따라서 이벤트는 각 이벤트와 관련된 포인트의 x 좌표로 우선순위를 정할 수 있다. Bentley-Otmann 알고리즘에서 잠재적 미래 이벤트는 아직 스윕되지 않은 선 세그먼트 끝점과 서로 바로 위 또는 아래에 있는 선 쌍을 포함하는 선 쌍의 교차점으로 구성된다.

알고리즘은 평면에서 스위프 라인 L 또는 그 위치를 명시적으로 유지할 필요가 없다. 오히려 L의 위치는 간접적으로 표현된다: 가장 최근에 처리된 사건과 관련된 지점을 통과하는 수직선이다.

바이너리 검색 트리는 빨간색-검은색 트리와 같은 균형 잡힌 이진 검색 트리 데이터 구조일 수 있다. 필요한 것은 삽입, 삭제 및 검색에 로그 시간이 걸리는 것이다. 마찬가지로 우선 순위 대기열은 이진 힙 또는 다른 로그 시간 우선 순위 대기열일 수 있으며, 피보나치 힙과 같은 보다 정교한 우선 순위 대기열은 필요하지 않다. 우선 순위 대기열의 공간 복잡성은 이를 구현하는 데 사용되는 데이터 구조에 따라 다르다는 점에 유의하십시오.

상세 알고리즘

벤틀리-오트만 알고리즘은 다음과 같은 단계를 수행한다.

1. 각각 평면의 한 점과 연관되고 점의 x 좌표로 우선순위가 지정되는 잠재적 미래 사건의 우선순위 큐 Q를 초기화한다. 따라서 처음에 Q는 입력 세그먼트의 각 엔드포인트에 대한 이벤트를 포함한다.
2. 교차점의 y 좌표로 정렬된 스위프 라인 L을 가로지르는 라인 세그먼트의 자체 균형 이진 검색 트리 T를 초기화한다. 처음에는 T가 비어 있다. (라인 스윕 L을 명시적으로 나타내지 않더라도, 처음에는 모든 입력 세그먼트의 왼쪽에 있는 수직선으로 상상하는 것이 도움이 될 수 있다.)
3. Q가 비어 있지 않은 동안 최소 x 좌표가 있는 p 지점과 연관된 Q에서 이벤트를 찾아 제거하십시오. 이 이벤트의 유형을 결정하고 다음 사례 분석에 따라 처리하십시오.
   • p가 선 세그먼트 s의 왼쪽 끝점인 경우, s를 T에 삽입한다. 각각 T에서 s 바로 위와 아래에 있는 라인 세그먼트 r과 t를 찾아라. r과 t의 교차(상태 데이터 구조에서 s의 인접)가 이벤트 대기열에서 잠재적 미래 이벤트를 형성하는 경우, 이벤트 대기열에서 가능한 미래 이벤트를 제거한다. s가 r 또는 t를 교차하는 경우, 교차점을 이벤트 대기열에서 잠재적 미래 이벤트로 추가한다.
   • p가 선 세그먼트 s의 오른쪽 끝점인 경우 T에서 s를 제거하십시오. (s 제거 전)이 각각 T(존재하는 경우)에서 그 바로 위와 아래에 있는 세그먼트를 찾는다. r과 t가 교차하는 경우, 교차점을 이벤트 대기열에 잠재적 미래 이벤트로 추가한다.
   • p가 두 세그먼트 s와 t(교차 왼쪽의 t 이하)의 교차점인 경우, t에서 s와 t의 위치를 교환한다. 스왑 후, 각각 t와 s 바로 아래 및 위에 있는 세그먼트 r과 u(있는 경우)를 찾는다. 이벤트 대기열에서 모든 교차점 rs(r과 s 사이의 교차점)와 tu(t와 u의 교차점)를 제거하고, r과 t가 교차하거나 s와 u가 교차하는 경우 해당 교차점을 이벤트 대기열에 추가한다.

분석

알고리즘은 유도에서 입증될 수 있는 바와 같이, 세그먼트 끝점 또는 교차점당 $하나$의 이벤트를 x ${\displaystyle$ x$}$ 좌표의$$ 정렬된 순서로 처리한다. 이는 일단 $i{\displaystyle }$ ${\displaystyle i}$ 이벤트가$$ 처리되면 다음 이벤트(교차점인 경우)는 $T{\displaystyle }$ ${\displaystyle T$로 대표되는 세그먼트의 순서에 인접하는 두 세그먼트의 교차여야 하며 알고리즘이 인접 세그먼트 사이의 모든 교차점을 잠재적 f로 유지하므로 뒤따른다.이벤트 대기열에 이벤트를 표시하므로 올바른 다음 이벤트가 항상 이벤트 대기열에 존재하게 된다. 결과적으로, 그것은 그것이 해결하기 위해 고안된 문제인 입력 라인 세그먼트의 모든 교차점을 정확하게 찾아낸다.

Bentley-Ottmann 알고리즘은 ${\displaystyle \mathrm{2n}}$+ k ${\displaystyle 2n+k}$개의$$ 이벤트를 처리하며, 여기서 $n{\displaystyle }$ ${\displaystyle n}$은 입력 라인 세그먼트 수를 나타내고$$ $k{\displaystyle }$ ${\displaystyle k}$은 교차 횟수를 나타낸다$$. 각 이벤트는 바이너리 검색 트리와 이벤트 대기열에서 일정한 수의 작업에 의해 처리되며, (부분 끝점과 인접 세그먼트 간의 교차만 포함하기 때문에) 이벤트 대기열에는 3n$${\$displaystyle 3n}$ 이상의 이벤트가$$ 포함되지 않는다. 모든 연산은 $O{\displaystyle \mathcal{}(\log }$ ${\displaystyle n}$) ${\displaystyle {\mathcal {O}(\$${\displaystyle \log }$ $n$ 따라서 ${\displaystyle \mathrm{알고리즘}}$의 총 시간은 $O{\displaystyle \mathcal{}(}$( n${\displaystyle }$+ k${\displaystyle }$) ${\displaystyle \mathrm{로그}\mathrm{logn}}$ )${\displaystyle$ {O$}(n+k)\log$ n$)}$이다$.$

알고리즘에 의해 발견된 교차점이 발견된 후 저장할 필요가 없는 경우, 임의의 시점에서 알고리즘이 사용하는 $공간$은 O${\displaystyle }$( ${\displaystyle n}$) ${\displaystyle {\mathcal{O}}}}$: 각 $n$$${\$displaystyle$n} 입력선 세그먼트는 2진수 검색 트리 T의 최대 한 노드에 해당하며, ev 위에 명시된 바와 같다.엔트 대기열에는 최대 ${\displaystyle \mathrm{3n}}$ ${\displaystyle 3n}$개의 요소가 포함되어$$ 있다. 이 공간 경계는 브라운(1981)에 기인한다. 알고리즘의 원래 버전은 약간 달랐다(다른 이벤트가 두 교차 세그먼트를 비인접적으로 만들 때 $Q$ ${\displaystyle Q}$에서 교차 이벤트를 제거하지 않아). 이로 인해 더 많은 공간을 사용하게 되었다.^[3]

Chen & Chan(2003)은 입력을 나타내는 배열의 세그먼트 순서에서 대부분의 정보를 인코딩하는 Bentley-Ottmann 알고리즘의 공간 효율적인 버전을 설명했으며, O$($ 2${\displaystyle {}^{}\mathrm{2n}}$ ) $displaystyle {\mathcal$ {O$}(\log ^{2}n)$ 추가$$ 메모리 셀만 필요로 했다. 그러나 암호화된 정보에 접근하기 위해 알고리즘은 로그 인자에 의해 느려진다.

특수 포지션

위의 알고리즘 설명은 라인 세그먼트가 수직이 아니며, 라인 세그먼트 끝점이 다른 라인 세그먼트에 있지 않으며, 교차점이 두 라인 세그먼트에 의해서만 형성되며, 두 개의 이벤트 포인트가 동일한 x 좌표를 가지지 않는다고 가정한다. 즉, 코너 케이스(즉, 입력 세그먼트의 엔드포인트의 일반적인 위치를 가정함)는 고려하지 않는다. 단, 이러한 일반적인 위치 가정은 선 세그먼트 교차로의 대부분의 적용에 합리적이지 않다. 벤틀리 & 오트만(1979)은 이러한 종류의 수치적 우연을 피하기 위해 입력을 약간 동요시킬 것을 제안했지만, 이러한 동요를 수행하는 방법에 대해서는 자세히 설명하지 않았다. de Berg 등. (2000) 특수 위치 입력 처리를 위한 다음 조치를 보다 상세히 기술한다.

• y 좌표를 사용하여 동일한 x 좌표로 사건 지점 간의 연결을 끊으십시오. y 좌표가 다른 이벤트는 이전과 같이 처리한다. 이 수정은 동일한 x 좌표를 가진 여러 사건 지점의 문제와 수직선 세그먼트의 문제를 모두 처리한다: 수직 세그먼트의 왼쪽 끝점은 낮은 y 좌표를 가진 것으로 정의되며, 그러한 세그먼트를 처리하는 데 필요한 단계는 비수직적 세를 처리하는 데 필요한 단계와 본질적으로 동일하다.경사가 매우 높은 gment
• 끝점을 포함하는 닫힌 집합으로 선 세그먼트를 정의하십시오. 따라서 끝점을 공유하는 두 개의 선 세그먼트 또는 다른 세그먼트의 끝점을 포함하는 선 세그먼트는 두 선 세그먼트의 교차점으로 계산된다.
• 여러 선 세그먼트가 동일한 지점에서 교차하는 경우, 해당 교차점에 대한 단일 사건 지점을 만들고 처리하십시오. 이 이벤트로 인해 발생하는 이진 검색 트리의 업데이트는 이것이 오른쪽 끝점인 라인 세그먼트를 제거하고, 왼쪽 끝점이 되는 라인 세그먼트를 새로 삽입하며, 이 이벤트 포인트를 포함하는 나머지 라인 세그먼트의 순서를 반대로 바꾸는 것을 포함할 수 있다. de Berg 등이 기술한 알고리즘 버전으로부터의 출력. (2000)는 교차하는 선분절 쌍의 집합이 아니라 선분절의 교차점 집합으로 구성된다.

퇴보성에 대한 유사한 접근법이 벤틀리-오트만 알고리즘의 LEDA 구현에 사용되었다.^[4]

수치 정밀도 문제

알고리즘의 정확성을 위해 라인 세그먼트 끝점과 다른 라인 세그먼트 사이의 상하의 관계를 근사치 없이 결정하고, 서로 다른 이벤트 포인트의 우선순위를 올바르게 지정할 필요가 있다. 이 때문에 입력선 세그먼트의 끝점에 정수 좌표를 사용하고, 임의의 정밀 산술법을 사용하여 두 세그먼트의 교차점에 대한 합리적 숫자 좌표를 정확하게 나타내는 것이 표준이다. 그러나 이러한 방법으로 계산된 값이 오차의 가능성 없이 사용될 수 있을 정도로 충분히 0에서 멀리 떨어져 있는지를 부동소수점 계산과 시험함으로써 이들 좌표의 계산과 비교 속도를 높일 수 있을 것이다.^[4] Bentley-Ottmann 알고리즘의 순전한 구현에 의해 요구되는 정확한 산술 계산은 입력 좌표보다 5배나 많은 정밀도를 필요로 할 수 있지만, Boissonat & Preparata(2000)는 입력 좌표보다 2배의 정밀도를 줄이는 알고리즘의 수정을 기술하고 있다.

더 빠른 알고리즘

계산의 대수적 의사결정 트리 모델에서 교차선 세그먼트 검출 문제에 대해 일치하는 하한이 있기 때문에 Bentley-Ottmann 알고리즘에 대한 시간 바운드의 O(n log n) 부분이 필요하다.^[5] 다만 교차 횟수인 k에 대한 의존도는 개선할 수 있다. Clarkson(1988)과 Mulmuley(1988)는 모두 평면 그래프를 구성하기 위한 무작위화된 알고리즘을 제공했는데, 이 그래프는 정점이 선 세그먼트의 끝점 및 교차점이고, 가장자리가 이러한 정점을 연결하는 부분의 일부인 평면 그래프를 예상 시간 O(n log n + k)에 제공하였고, 이러한 배열 문제는 결정적으로 해결되었다. Chazelle & Edelsbrunner(1992)에 의해 바인딩된 동일한 O(n log n + k) 시간에. 그러나 이 배열을 전체적으로 구성하려면 Bentley-Ottmann 알고리즘의 O(n) 공간보다 큰 공간 O(n + k)가 필요하다. 발라반(1995)은 시간 O(n log n + k)와 공간 O(n)의 모든 교차를 나열하는 다른 알고리즘을 기술했다.

입력선 세그먼트와 그 끝점이 연결된 그래프의 가장자리와 정점을 형성하는 경우(아마도 교차점이 있을 것이다), Bentley-Otmann 알고리즘에 바인딩된 시간의 O(n log n) 부분도 감소할 수 있다. Clarkson, Cole & Tarjan(1992)이 보여주듯이, 이 경우 예상 시간 O(n log* n + k)에 문제를 해결하기 위한 임의화된 알고리즘이 있다. 여기서 log*는 로그보다 훨씬 느리게 성장하는 기능인 반복 로그(returated logarithm)를 나타낸다. Eppstein, Goodrich & Strash(2009)의 밀접하게 연관된 랜덤화 알고리즘은 로그가⁽ⁱ⁾ 로그 함수 i를 반복하여 얻은 함수를 나타내는 임의의 상수 i에 대해 시간 O(n + k logn⁽ⁱ⁾)로 동일한 문제를 해결한다. 이러한 알고리즘 중 첫 번째 알고리즘은 k가 logn⁽ⁱ⁾ factor에 의해 n보다 클 때마다 선형 시간이 걸리는 반면, 두 번째 알고리즘은 k가 logn⁽ⁱ⁾ factor에 의해 n보다 작을 때마다 선형 시간이 걸린다. 이 두 알고리즘 모두 입력의 작은 무작위 샘플에 Bentley-Otmann 알고리즘을 적용하는 것을 포함한다.

메모들

참조

• Balaban, I. J. (1995), "An optimal algorithm for finding segments intersections", Proc. 11th ACM Symp. Computational Geometry, pp. 211–219, doi:10.1145/220279.220302, S2CID 6342118.
• Bartuschka, U.; Mehlhorn, K.; Näher, S. (1997), "A robust and efficient implementation of a sweep line algorithm for the straight line segment intersection problem", in Italiano, G. F.; Orlando, S. (eds.), Proc. Worksh. Algorithm Engineering, archived from the original on 2017-06-06, retrieved 2009-05-27.
• Bentley, J. L.; Ottmann, T. A. (1979), "Algorithms for reporting and counting geometric intersections", IEEE Transactions on Computers, C-28 (9): 643–647, doi:10.1109/TC.1979.1675432, S2CID 1618521.
• de Berg, Mark; van Kreveld, Marc; Overmars, Mark; Schwarzkopf, Otfried (2000), "Chapter 2: Line segment intersection", Computational Geometry (2nd ed.), Springer-Verlag, pp. 19–44, ISBN 978-3-540-65620-3.
• Boissonat, J.-D.; Preparata, F. P. (2000), "Robust plane sweep for intersecting segments" (PDF), SIAM Journal on Computing, 29 (5): 1401–1421, doi:10.1137/S0097539797329373.
• Brown, K. Q. (1981), "Comments on "Algorithms for Reporting and Counting Geometric Intersections"", IEEE Transactions on Computers, C-30 (2): 147, doi:10.1109/tc.1981.6312179, S2CID 206622367.
• Chazelle, Bernard; Edelsbrunner, Herbert (1992), "An optimal algorithm for intersecting line segments in the plane", Journal of the ACM, 39 (1): 1–54, doi:10.1145/147508.147511, S2CID 785741.
• Chen, E. Y.; Chan, T. M. (2003), "A space-efficient algorithm for segment intersection", Proc. 15th Canadian Conference on Computational Geometry (PDF).
• Clarkson, K. L. (1988), "Applications of random sampling in computational geometry, II", Proc. 4th ACM Symp. Computational Geometry, pp. 1–11, doi:10.1145/73393.73394, S2CID 15134654.
• Clarkson, K. L.; Cole, R.; Tarjan, R. E. (1992), "Randomized parallel algorithms for trapezoidal diagrams", International Journal of Computational Geometry and Applications, 2 (2): 117–133, doi:10.1142/S0218195992000081. Corrigendum, 2: 341–343.
• Eppstein, D.; Goodrich, M.; Strash, D. (2009), "Linear-time algorithms for geometric graphs with sublinearly many crossings", Proc. 20th ACM-SIAM Symp. Discrete Algorithms (SODA 2009), pp. 150–159, arXiv:0812.0893, Bibcode:2008arXiv0812.0893E, doi:10.1137/090759112, S2CID 13044724.
• Mulmuley, K. (1988), "A fast planar partition algorithm, I", Proc. 29th IEEE Symp. Foundations of Computer Science (FOCS 1988), pp. 580–589, doi:10.1109/SFCS.1988.21974, S2CID 34582594.
• O'Rourke, J. (1998), "Section 7.7: Intersection of segments", Computational Geometry in C (2nd ed.), Cambridge University Press, pp. 263–265, ISBN 978-0-521-64976-6.
• Preparata, F. P.; Shamos, M. I. (1985), "Section 7.2.3: Intersection of line segments", Computational Geometry: An Introduction, Springer-Verlag, pp. 278–287, Bibcode:1985cgai.book.....P.
• Pach, J.; Sharir, M. (1991), "On vertical visibility in arrangements of segments and the queue size in the Bentley–Ottmann line sweeping algorithm", SIAM Journal on Computing, 20 (3): 460–470, doi:10.1137/0220029, MR 1094525.
• Shamos, M. I.; Hoey, Dan (1976), "Geometric intersection problems", 17th IEEE Conf. Foundations of Computer Science (FOCS 1976), pp. 208–215, doi:10.1109/SFCS.1976.16, S2CID 124804.

외부 링크

• Smid, Michiel (2003), Computing intersections in a set of line segments: the Bentley–Ottmann algorithm (PDF).