Abstract
由於電子技術的進步神速，各種平行計算機結構紛紛被提出；其中，網狀 連結計算機由於其架構簡單而有規則，至今仍受到重視，然而由於其結構 所導致之直徑太大，使其在長距離通訊上之效率較差，對於一些含長距離 通訊之應用，採用網狀連結計算機，並不適合。因此，許多研究均在探討 如何加強其處理機間之連結架構以改進其缺點。在這些研究當中，一種很 有效率的方法便是在網狀連結方式以外加入具有廣播功能的巴士。因為這 種多重處理機架構的特性，用來處理圖形和影像的問題會有不錯的結果， 而這類研究方向中又以凸殼問題為首要。本篇論文便是探討在具有可重組 巴士的網狀連結計算機上面，對於解決凸殼多邊形問題的平行演算法之研 究。本論文探討在具有可重組巴士的網狀連結計算機上的平行演算法之設 計。具有可重組巴士的網狀連結計算機最大的特點在於其負責連結處理單 元的可重組巴士系統，可重組巴士為一種可動態地調整處理單元間連結組 態的廣播巴士，因此我們可以根據問題本身的通訊需求，動態地調整組態 以達到最有效率的處理機連結。在具有可重組巴士的網狀連結計算機上面 ，給定一張以白色為背景數個黑點的影像為輸入，我們介紹一個平行演算 法能有效的找出包含這些黑點的凸殼多邊形。接下來提出五個平行演算法 解決一些凸殼多邊形的相關運算。首先，我們將偵測一特定點是否包含在 所給定的凸殼多邊形內；利用這個結果，我們設計出一個方法，來判斷一 個給定的凸殼多邊形是否包含在另一已知的凸殼多邊形。第三個欲探討的 問題是計算一給定之凸殼多邊形的面積。最後，我們設計了二個平行演算 法，將分別用來計算一凸殼多邊形的寬度和直徑。