검색 기능은 준비 중입니다.
검색 기능은 준비 중입니다.

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice

Round Optimal Parallel Algorithms for the Convex Hull of Sorted Points 정렬된 점의 볼록 껍질에 대한 라운드 최적 병렬 알고리즘

Naoki OSHIGE, Akihiro FUJIWARA

  • 조회수

    0

  • 이것을 인용

요약 :

본 논문에서는 정렬된 점의 볼록 껍질에 대한 결정론적 병렬 알고리즘과 관련 문제에 대한 적용을 제시합니다. 알고리즘은 CGM(Coarse Grained Multicomputer) 모델에 대해 제안되었습니다. 우리는 먼저 일정한 수의 통신 라운드로 문제를 계산하기 위한 비용 최적 병렬 알고리즘을 제안합니다. n/p p2어디로 n 는 입력의 크기이고 p 프로세서 수입니다. 다음으로 우리는 더 복잡한 비용 최적 알고리즘을 제안합니다. n/p pε, 여기서 0 < ε < 2입니다. 위의 두 결과로부터 다음과 같이 정렬된 점의 볼록 껍질을 계산할 수 있습니다. O(n/p) 계산 시간과 일정한 통신 라운드 수 n/p pε, 여기서 ε > 0입니다. 마지막으로 볼록 껍질 알고리즘의 적용을 보여줍니다. 우리는 볼록 레이어를 해결합니다. d 라인 O((n 기록 n)/p) 일정한 통신 라운드 수로 계산 시간. 또한 알고리즘은 문제에 대해 비용 최적입니다.

발행
IEICE TRANSACTIONS on Fundamentals Vol.E84-A No.5 pp.1152-1160
발행일
2001/05/01
공개일
온라인 ISSN
DOI
원고의 종류
Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
범주

작성자

키워드