计算机科学
計算機科學
계산궤과학
COMPUTER SCIENCE
2013年
2期
16-19,57
,共5页
颜坚%毕硕本%汪大%郭忆
顏堅%畢碩本%汪大%郭憶
안견%필석본%왕대%곽억
凸壳%并行计算%多核%颜氏距离
凸殼%併行計算%多覈%顏氏距離
철각%병행계산%다핵%안씨거리
改进了周培德的Z3-2算法,提出一种在多核架构下计算平面点集凸壳的并行算法.用“颜氏距离”来数字化平面上点与有向线段的位置关系,减少了计算次数和时间.进一步将原算法中比较耗时的两个过程分别在O(1)的时间复杂度内进行迭代分解,即当原问题规模大于给定阈值时,将原问题分解为若干个独立的子问题,若所得子问题的规模仍大于给定阈值,则再对子问题进行分解；所有子问题被加入并行任务组进行并行求解以充分利用多核处理器的并行计算资源.给出了算法的正确性说明,实验结果也表明本算法稳定高效.
改進瞭週培德的Z3-2算法,提齣一種在多覈架構下計算平麵點集凸殼的併行算法.用“顏氏距離”來數字化平麵上點與有嚮線段的位置關繫,減少瞭計算次數和時間.進一步將原算法中比較耗時的兩箇過程分彆在O(1)的時間複雜度內進行迭代分解,即噹原問題規模大于給定閾值時,將原問題分解為若榦箇獨立的子問題,若所得子問題的規模仍大于給定閾值,則再對子問題進行分解；所有子問題被加入併行任務組進行併行求解以充分利用多覈處理器的併行計算資源.給齣瞭算法的正確性說明,實驗結果也錶明本算法穩定高效.
개진료주배덕적Z3-2산법,제출일충재다핵가구하계산평면점집철각적병행산법.용“안씨거리”래수자화평면상점여유향선단적위치관계,감소료계산차수화시간.진일보장원산법중비교모시적량개과정분별재O(1)적시간복잡도내진행질대분해,즉당원문제규모대우급정역치시,장원문제분해위약간개독립적자문제,약소득자문제적규모잉대우급정역치,칙재대자문제진행분해；소유자문제피가입병행임무조진행병행구해이충분이용다핵처리기적병행계산자원.급출료산법적정학성설명,실험결과야표명본산법은정고효.
