스위프 라인 알고리즘

계산 기하학에서 스위프 라인 알고리즘이나 평면 스위프 알고리즘은 개념 스위프 라인이나 스위프 표면을 사용하여 유클리드 공간의 다양한 문제를 해결하는 알고리즘 패러다임이다.그것은 계산 기하학의 핵심 기법 중 하나이다.

이런 유형의 알고리즘 뒤에 있는 생각은 어떤 선(종종 수직선)이 어떤 지점에서 정지하면서 비행기를 휩쓸거나 이동한다고 상상하는 것이다.기하학적 연산은 정지할 때마다 스윕 라인 바로 근처에 있거나 교차하는 기하학적 객체로 제한되며, 선이 모든 객체를 통과하면 완전한 솔루션을 사용할 수 있다.

역사

이 접근방식은 컴퓨터 그래픽 렌더링의 스캔라인 알고리즘으로 추적될 수 있으며, 전체 설명이 메모리에 맞지 않기 때문에 IC에 대한 기하학적 설명이 병렬 스트립으로 처리된 통합 회로 배치 설계의 초기 알고리즘에서 이 접근방식을 이용하게 된다.^{[citation needed]}

적용들

샤모스와 호이가 평면 내 선분할 교차로에 대한 알고리즘을 제시했을 때 기하학적 알고리즘의 계산적 복잡성에 돌파구가 마련되었고, 특히 그들은 효율적인 데이터 구조(자체 균형 바이너리 검색 트리)와 스캔라인 접근방식을 결합하여 어떻게 그것을 포지셔닝할 수 있는지를 기술했다.O(N 로그 N)의 시간 복잡도에서 평면 내 N 세그먼트 사이에 교차점이 있는지 여부를 검출할 수 있다.^[1]밀접하게 연관된 Bentley-Otmann 알고리즘은 Sweep line 기법을 사용하여 O(N + K) 로그 N의 복잡성과 O(N)의 공간 복잡성을 시간적으로 보고한다.^[2]

그 이후, 이 접근방식은 보로노이 다이어그램(Fortune의 알고리즘)의 구성과 폴리곤의 델라우나이 삼각측량 또는 부울 연산 등 여러 문제에 대한 효율적인 알고리즘을 설계하기 위해 사용되었다.

일반화 및 확장

위상학적 스위프는 처리 지점의 완만한 순서를 가진 평면 스위프의 한 형태로서, 점을 완전히 분류할 필요가 없다. 일부 스위프 라인 알고리즘을 더 효율적으로 수행할 수 있다.

기하학적 알고리즘을 설계하기 위한 회전 캘리퍼스 기법은 입력 평면의 투사적 이중에서 평면 스위프의 한 형태로 해석될 수 있다: 투사적 이중성의 형태는 한 평면의 선의 기울기를 이중 평면의 한 점의 x 좌표로 변환하므로, 그 기울기에 따라 정렬된 순서대로 선을 통과하는 진행은 a.회전 캘리퍼스 알고리즘에 의해 수행되는 s는 평면 스위프 알고리즘에서 x-11에 의해 정렬된 지점을 통과하는 진행에 이중적이다.

광범위한 접근방식은 더 높은 차원으로 일반화할 수 있다.

참조