單一通道擴散式溝通系統之演算法則

Abstract

於本論文中，我們在單一通道擴散式溝通系統 ( Single-Channel Broadcast Commun icationSystem ) 上，設計平面處理之計算方法。我們針對下列三個問題提出解決之 方法﹕平面俯控多邊形 ( the dominance hull ) 之計算，平面凸多邊形 ( the con vex hull )之建立，以及無向圖形中最小展開樹 ( the minimum spanning tree for an undirected graph )之找尋。首先，我們找出了在此系統上，解決前兩個問題所 需的最少時間和最少擴散次數；同時，提出了最佳的解決方法。另外，我們也提出了 無向圖形中最小展開樹之找尋方法，其執行時間最多不超過 O ( n log n )。