| [ QuizWit ] in KIDS 글 쓴 이(By): cdpark (박종대) 날 짜 (Date): 1998년 6월 6일 토요일 오후 07시 53분 13초 제 목(Title): [정리] 다각형 사이의 교차에 대해서... 이런 문제를 가장 잘 다루는 분야는 바로 "Computational Geometry".. 바로 제가 두번째 관심이 있는 분야입니다. (첫번째는 Algorithmic Graph Theory) A. 우선 두 다각형이 겹칠 경우, 몇개의 만나는 점이 생기느냐란 문제가 있습니다. 두 p각형과 q각형이 있을 때, 1. 둘 다 볼록 다각형이면? min(2p,2q) 개의 교차점이 있을 수 있습니다. 2. 둘 중 하나만 볼록 다각형이면? max(2p,2q) 개의 교차점이 있을 수 있습니다. 3. 둘 다 임의의 다각형이면? pq 개의 교차점이 있을 수 있습니다. B. 두 다각형이 교차하는지를 검사하는 문제가 있습니다. 이제부터는 편의를 위해서 n = p+q 로 사용하겠습니다. 1. 둘 다 볼록 다각형이면? 1-1. 전처리 없이 O(n) 시간에 동작하는 알고리즘이 있습니다. 1-2. O(n) 시간의 전처리 후에 O(log n) 시간에 동작하는 알고리즘이 있습니다. 1-2의 경우엔 여러 볼록다각형에 대한 처리를 할 때는 유리하겠죠. 2. 둘 다 임의의 다각형이면? 1-1. 전처리 없이 O(n) 시간에 동작하는 알고리즘이 있습니다. 1-2. O(n) 시간의 전처리 후에 O(m log n) 시간에 동작하는 알고리즘이 있습니다. (이때, m은 minimum link withness란 값으로 m<=n입니다.) C. 실제 교차하는 영역을 구하는 알고리즘 1. 둘 다 볼록다각형이면? O(n) 시간에 구할 수 있습니다. 2. 둘 다 임의의 다각형이면? 결과가 k 개의 꼭지점을 포함한다면, O(n lon n + k) 시간에 답하는 알고리즘이 있습니다. D. 3차원 다면체에 대한 결과들... 1. 두 3차원 볼록다면체 p면체와 q면체가 교차하는지 검사하는 알고리즘은 O(p+q) 시간의 전처리 후에 O(log p * log q) 시간에 검사할 수 있음이 알려져 있습니다. 2. 두 3차원 볼록다면체 p면체와 q면체의 교차 영역을 구하는 O(p+q) 시간의 알고리즘이 알려져 있습니다. -- 박.. |