스위프 라인 알고리즘 - Wikipedia

본문으로 이동

메인 메뉴

메인 메뉴

사이드바로 이동 숨기기

탐색

기여

검색

모양

개인 도구

스위프 라인 알고리즘

7개 언어

링크 편집

영어

도구

도구

사이드바로 이동 숨기기

작업

일반

인쇄/내보내기

다른 프로젝트에서

Wikidata 항목

모양

사이드바로 이동 숨기기

생일 모드 (Baby Globe)

비활성화 활성화 생일 모드에 대해 자세히 알아보기

텍스트

작게 표준 크게

이 문서는 항상 작은 글꼴 크기를 사용합니다

너비

표준 넓게

콘텐츠는 브라우저 창에 가능한 한 넓게 표시됩니다.

색상 (베타)

자동 밝게 어둡게

이 문서는 항상 밝은 모드입니다.

Wikipedia, the free encyclopedia에서

기하학적 문제를 해결하기 위해 움직이는 선을 사용하는 알고리즘의 한 부류

Voronoi diagrams를 구성하기 위한 스위프 라인 기법인 Fortune's algorithm의 애니메이션.

computational geometry에서 스위프 라인 알고리즘 또는 평면 스위프 알고리즘은 다양한 Euclidean space의 문제를 해결하기 위해 개념적인 스위프 라인 또는 _스위프 표면_을 사용하는 algorithmic paradigm이다. 이는 계산기하학에서 핵심적인 기법 가운데 하나이다.

이 유형의 알고리즘 뒤에 있는 아이디어는 하나의 선(종종 수직선)을 평면 전체에 걸쳐 쓸어가듯 이동시키며, 특정 지점들에서 멈춘다고 상상하는 것이다. 기하학적 연산은 선이 멈출 때마다 스위프 라인과 교차하거나 그 바로 근처에 있는 기하 객체들로 제한되며, 선이 모든 객체 위를 지나가고 나면 완전한 해가 얻어진다.

활용

[편집]

이 접근법의 한 응용은 Shamos와 Hoey가 1976년에 평면에서의 line segment intersection 알고리즘을 제시했을 때 기하 알고리즘의 computational complexity에서 돌파구를 가져왔다. 특히 그들은 스캔라인 접근법과 효율적인 자료구조(self-balancing binary search trees)를 결합하면 평면 위의 N개 선분 사이에 교차가 존재하는지 time complexity O(N log N) 안에 판별할 수 있음을 설명했다.[1] 밀접하게 관련된 Bentley–Ottmann algorithm은 스위프 라인 기법을 사용하여 평면 위의 임의의 N개 선분 사이의 모든 K개 교차를 시간 복잡도 O((N + K) log N)와 공간 복잡도 O(N)로 보고한다.[2]

그 이후 이 접근법은 Voronoi diagram의 구성(Fortune's algorithm)과 Delaunay triangulation 또는 boolean operations on polygons 같은 계산기하학의 여러 문제를 위한 효율적인 알고리즘을 설계하는 데 사용되어 왔다.

일반화와 확장

[편집]

위상적 스위핑은 처리 지점의 단순한 순서를 사용하는 평면 스위프의 한 형태로, 점들을 완전히 정렬해야 하는 필요를 피하게 해 주며, 일부 스위프 라인 알고리즘을 더 효율적으로 수행할 수 있게 한다.

기하 알고리즘 설계를 위한 rotating calipers 기법 역시 입력 평면의 projective dual에서의 평면 스위프의 한 형태로 해석될 수 있다. 사영 쌍대성의 한 형태는 한 평면에서 직선의 기울기를 쌍대 평면에서 점의 x-좌표로 변환하므로, rotating calipers 알고리즘이 수행하는 기울기순으로 정렬된 직선들을 따라가는 진행은 평면 스위프 알고리즘에서 x-좌표순으로 정렬된 점들을 따라가는 진행과 쌍대 관계에 있다.[3]

스위핑 접근법은 더 높은 차원으로 일반화될 수 있다.[4]

참고문헌

[편집]

^Shamos, Michael I.; Hoey, Dan (1976), "Geometric intersection problems", Proc. 17th IEEE Symp. Foundations of Computer Science (FOCS '76), pp.208–215, doi:10.1109/SFCS.1976.16, S2CID 124804.
^Souvaine, Diane (2008), Line Segment Intersection Using a Sweep Line Algorithm(PDF).
**^**Cheung, Yam Ki; Daescu, Ovidiu (2009). "Line segment facility location in weighted subdivisions". In Goldberg, Andrew V.; Zhou, Yunhong (eds.). Algorithmic Aspects in Information and Management, 5th International Conference, AAIM 2009, San Francisco, CA, USA, June 15-17, 2009. Proceedings. Lecture Notes in Computer Science. Vol.5564. Springer (1). pp.100–113. doi:10.1007/978-3-642-02158-9_10. ISBN 978-3-642-02157-2.
**^**Sinclair, David (2016-02-11). "A 3D Sweep Hull Algorithm for computing Convex Hulls and Delaunay Triangulation". arXiv:1602.04707 [cs.CG].