본문 바로가기
HOME> 논문 > 논문 검색상세

논문 상세정보

정보과학회논문지. Journal of KIISE. 시스템 및 이론 v.28 no.3, 2001년, pp.155 - 160   피인용횟수: 1

$L_\infty(L_1)$디루니 삼각분할의 병렬처리 알고리즘
A Parallel Algorithm for Constructing the Delaunay Triangulation in the$L_\infty(L_1)$ Metric

위영철   (아주대학교 정보 및 컴퓨터공학부UU0000892  );
  • 초록

    본 논문은 영역별 근접 그래프 (geographic nearest neighbor graph)와 레인지 트리 (range tree)를 이용하여 평면 위의 n 개의 점에 대한 L $_{\infty}$ (L $_1$ ) 거리 (metric) 상의 디루니 삼각분할 (Delaunay triangulation)을 구축하는 방법을 소개한다. 이 방법은 L $_{\infty}$ (L $_1$ ) 거리 상에서 디루니 삼각분할에 있는 각 삼각형의 최소한 한 선분이 영역별 근접 그래프에 포함됨을 이용하여 레인지 트리 방법으로 디루니 삼각분할을 구축한다. 본 방법은 0(nlogn)의 순차계산 시간에 L $_{\infty}$ (L $_1$ ) 디루니 삼각분할을 구축하며, CREW-PRAM (Concurrent Read Exclusive Write Parallel Random Access Machine)에서 0(n)의 프로세서로 0(logn)의 병렬처리 시간에 L $_{\infty}$ (L $_1$ ) 디루니 삼각분할을 구축한다. 또한, 이 방법은 직선간의 교차점 계산 대신 거리비교를 하기 때문에 수치오차가 적고 구현이 용이하다.


  • 참고문헌 (16)

    1. A.C. Yao, On Constructing Minimum Spanning Trees in k-dimensional Spaces and Related Problems, SIAM J. Comput. 11(4), 721-736, 1982 
    2. K.J. Supowit, The Relative Neighborhood Graph, with an Application to Minimum Spanning Trees, J.ACM 30(3), 428-448, 1983 
    3. Y.C. Wee and S. Chaiken and S. S. Ravi, Rectilinear Steiner Tree Heuristics and Minimum Spanning Tree Algorithms Using Geographic Nearest Neighbors, Algorithmica 12, 421-435, 1994 
    4. D.E. Willard and Y. C. Wee, Quasi-valid Range Querying and its Implications for Nearest Neighbor Problems, Proceedings of the Fourth Annual Symp. on Computational Geometry, 34-43, 1988 
    5. D.T. Lee and C. K. Wong, Voronoi Diagrams in $L_1(L_{\infty})$ Metrics with 2-Dimensional Storage Applications, SIAM J. Comput. 9(1), 200-211, 1980 
    6. E. Papadopoulou and D.T. Lee, Critical Area Computation via Voronoi Diagrams, IEEE Transactions on Computer Aided Design of Integrated Circuits and Systems, 18(4), 463-474, 1999 
    7. W. Preilowski and W. Mumbeck, A Time-Optimal parallel Algorithm for the Computing of Voronoi diagrams, Lecture Notes in Computer Science, Springer Verlag, 424-433, 1988 
    8. P. Su, R.L. Drysdale, A Comparison of Sequential Delaunay Triangulation Algorithm, Computational Geometry 7, 361-385, 1997 
    9. H.N. Gabow, J.L. Bentley and R. E. Tarjan, Scaling and Related Techniques for Geometry Problems, Proc. 16st Ann Symp. Theory of Computing, 135-143, 1984 
    10. L.J. Guibas and J. Stolfi, On Computing all North-east Nearest Neighbors in the $L_1$ Metric, Info. Process. Lett. 17, 219-223, 1983 
    11. J. Katajainen, The Region Approach for Computing Relative Neighborhood Graphs in the $L_p$ Metric, Computing 40, 147-161, 1988 
    12. D.T. Lee, Two-dimensional Voronoi Diagrams in the $L_p$-Metric, J.ACM 27(4), 604-618, 1980 
    13. M.J. Atallah, R. Cole, and M.T. Goodrich, Divide-and-Conquer: A Technique for Designing Parallel Algorithms, 28th IEEE Symp. on Foundations of Computer Science, Tech. Rep. 665, Dept. of Comp. Sci., Purdue Univ., 151-160, 1987 
    14. A. Aggarwal, B. Chazelle, L. Guibas, C. O'Dunlaing and C. Yap, Parallel Comutational Geometry, Algorithmica, 293-327, 1988 
    15. R. Cole, M.T. Goodrich, Optimal Parallel Algorithms for Polygon and Point-Set Problems, Proc. of the Fourth Ann. Symp. on Computational Geometry, 201-210, 1988 
    16. K. Clarkson, Approximation Problems for Shortest Path Motion Planning, Proc. 19th Ann. ACM Symp. Theory of Computing, 56-65, 1987 
  • 이 논문을 인용한 문헌 (1)

    1. Lee, Jun ; Kim, Ji-In 2002. "A Contour Generation Algorithm for Visualizing Non-Lattice Type Data" 정보과학회논문지. Journal of KIISE. 시스템 및 이론, 29(2): 94~104     

 저자의 다른 논문

  • 위영철 (19)

    1. 1999 "Bzier 방법을 이용한 B-spline의 차수 감소" 정보과학회논문지. Journal of KISS (a):computer systems and theory. A 26 (8): 875~883    
    2. 2000 "정수 연산에 의한 그래픽스 프리미티브 랜더링 방법" 컴퓨터그래픽스학회논문지 = Journal of the Korea Computer Graphics Society 6 (3): 1~7    
    3. 2000 "L(L1) 동적 디루니 삼각분할 방법" 컴퓨터그래픽스학회논문지 = Journal of the Korea Computer Graphics Society 6 (4): 23~28    
    4. 2001 "단조 행렬 탐색을 이용한 양방향 각도제한 근접점 계산방법" 정보과학회논문지. Journal of KIISE. 시스템 및 이론 28 (1): 64~72    
    5. 2001 "정규화된 분산을 이용한 프랙탈 압축방법" 정보처리학회논문지. The KIPS transactions. Part A. Part A a8 (4): 499~502    
    6. 2001 "프랙탈 이미지 압축을 위한 분산 기반 유사 블록 탐색 연구" 컴퓨터그래픽스학회논문지 = Journal of the Korea Computer Graphics Society 7 (1): 11~17    
    7. 2003 "이전 프레임의 시공간 모션 정보에 의한 예측 탐색 알고리즘" 컴퓨터그래픽스학회논문지 = Journal of the Korea Computer Graphics Society 9 (3): 23~29    
    8. 2003 "십자와 육각패턴을 이용한 고속 블록 정합 동작 예측 기법" 정보처리학회논문지. The KIPS transactions. Part B. Part B b10 (7): 811~814    
    9. 2004 "움직임 벡터 예측 후보들과 적응적인 탐색 패턴을 이용하는 블록 정합 알고리즘" 정보처리학회논문지. The KIPS transactions. Part B. Part B b11 (3): 247~256    
    10. 2004 "단위 다이아몬드와 납작한 육각패턴을 이용한 고속 블록 정합 알고리즘" 정보과학회논문지. Journal of KISS : Computing practices. 컴퓨팅의 실제 10 (1): 57~65    

 활용도 분석

  • 상세보기

    amChart 영역
  • 원문보기

    amChart 영역

원문보기

무료다운로드
  • NDSL :
유료다운로드

유료 다운로드의 경우 해당 사이트의 정책에 따라 신규 회원가입, 로그인, 유료 구매 등이 필요할 수 있습니다. 해당 사이트에서 발생하는 귀하의 모든 정보활동은 NDSL의 서비스 정책과 무관합니다.

원문복사신청을 하시면, 일부 해외 인쇄학술지의 경우 외국학술지지원센터(FRIC)에서
무료 원문복사 서비스를 제공합니다.

NDSL에서는 해당 원문을 복사서비스하고 있습니다. 위의 원문복사신청 또는 장바구니 담기를 통하여 원문복사서비스 이용이 가능합니다.

이 논문과 함께 출판된 논문 + 더보기