http://chineseinput.net/에서 pinyin(병음)방식으로 중국어를 변환할 수 있습니다.
변환된 중국어를 복사하여 사용하시면 됩니다.
L<sub>∞</sub>(L<sub>1</sub>) 동적 디루니 삼각분할 방법
위영철,김하진,서상구,Wee, Youngcheul,Kimn, Hajine,Seo, Sangku 한국컴퓨터그래픽스학회 2000 컴퓨터그래픽스학회논문지 Vol.6 No.4
본 논문은 평면 위의 n 개의 점에 대한 $L_{\infty}(L_1)$ 거리의 동적 디루니 삼각분할을 구축하는 방법을 소개한다. 이 방법은 $L_{\infty}(L_1)$ 거리 상에서 사분면 근접 그래프가 디루니 삼각분할에 포함되고 디루니 삼각분할에 있는 각 삼각형의 최소한 한 선분이 사분면 근접 그래프에 포함됨을 발견하고 이를 이용하여 레인지 트리 방법으로 동적 디루니 삼각분할을 구축한다. 본 방법은 $L_1(L_{\infty})$ 거리의 디루니 삼각분할에서 삽입과 삭제를 한 점 당 $O(log^2n)$ amortized 시간과 O(log n)의 expected 시간에 처리한다. We introduce a new method for constructing a dynamic Delaunay triangulation for a set S of n sites in the plane under the $L_{\infty}(L_1)$ metric. We find that the quadrant neighbor graph is contained in the Delaunay triangluation and that at least one edge of each triangle in the Delaunay triangulation is contained in the quadrant neighbor graph. By using these observations and employing a range tree scheme, we present a method that dynamically maintains the $L_{\infty}(L_1)$ Delaunay triangulation under insertions and deletions in $O(log^2n)$ amortized time and O(log n) expected time.
위영철(Youngcheul Wee),김하진(Hajin Kimn) 한국정보과학회 2000 한국정보과학회 학술발표논문집 Vol.27 No.2Ⅰ
이 논문은 행렬탐색 방법을 이용하여 평면상의 n 개의 점에 대한 L_p, 1≤p≤∞ 거리의 양방향 각도제한 근접 점 문제를 θ(n log n) 시간에 계산하는 알고리즘을 고안한다. 이 방법은 최적의 시간 복잡도를 가지며 궤적추적 법을 쓰지 않기 때문에 구현이 용이하고 실용적이다.