구 볼록 다각형들의 분리 및 교차를 위한 간선 기반 알고리즘의 구현

하종성, 천은홍 · 2001

본 논문에서는 구상에서 주어진 볼록 다각형의 집합 Γ={P₁,…,Pn}의 최대 또는 최소 교차를 결정하기 위하여 다각형의 간선으로 구를 면으로 분할하는 문제를 고려한다. 이 문제는 Γ의 최대 부분집합을 포함하는 반구를, Γ를 분리하는 대원을, Γ를 이분하는 대원을, Γ를 최소 또는 최대 부분집합을 교차하는 대원을 각각 찾는 다섯 가지 기하적 문제와 공통적으로 관련이 있다. 구다각형의 최대 및 최소 교차를 효율적으로 구하기 위하여 우리는 간선 기반 분할의 방식을 취하는데이 방식에서는 구가 각 다각형에 의해 증분적으로 분할되면서 면이 아닌 면을 구성하는 간선의 소유권이 처리된다. 마지막에는 최대수의 소유권을 가지는 분할된 비정렬 간선들을 모아 해가 되는 면들의 경계를 구성하지 않고 그들의 중심을 근사적으로 얻는다. 최대 교차를 찾는 우리의 알고리즘은 효율적인 시간복잡도 O(nv)를 가지는 것으로 분석된다. 여기서 n과 v은 각각 다각형과 모든 정점의 개수들이다. 더구나 견고하게 수치를 계산하고 모든 degeneracy 경우를 다루기 때문에 구현의 관점에서도 실제적이다. 유사한 방식을 사용하여 일반적인 교차의 모든 경계는 O(nv+LlogL) 시간에 구성할 수 있다. 여기서 L은 해로 출력되는 간선의 개수이다.

Cited by 0 works.

Authors