最短路徑問題的研究，在現今的機器人學中可幫助機器人自動計算出最佳的移動路徑
。同時，這類問題在計算幾何學中，也有它理論研究的價值。本篇論文便是以理論研
究的觀點來探討這類問題中的一個特例：找出兩點間避開三度空間中ｋ個凸多面體障
礙物的最短路徑。根據Sharir的研究，這種最短路徑經過一個組合邊序列。這個組合
邊序列是由所有被此最短路徑經過的凸多面體，各提供一個邊序列所組合而成，而一
個邊序列是由一連串相鄰凸多面體的邊所組成。假如我們稱被一任意兩點間的最短路
徑經過的邊序列為最短邊序列，在找ｋ個凸多面體事所有最短邊序列後，可以嘗試所
有凸多面體上邊序列的組合，而找到一個組合邊序列是最短路徑經過的組合邊序列。
在找到最短路徑過的組合邊序列後，可用已有的方法來找出真正的最短路徑。Sharir
提出一個方法，並證明在一個凸多面體上最多ｎ的７次方個邊序列屬於最短邊序列，
其中，ｎ為凸多面體的總邊數。Sharir的方法會找出一些非最邊序列的邊序列。因此
我們必須嘗試ｎ的７ｋ 次方種組合邊序列才可找到最短路徑。Mount 曾舉出一個例
子，證明在最壞的情形下，一個凸多面體上至少ｎ的４次方個最短邊序列。在本篇論
文中，我們提出一個方法可一一找出所有最短邊序列，而絕不包含非最短邊序列的邊
序列，所以我們只要嘗試最少種組合邊序列，便可找出最短路徑。Sharir猜測在最壞
的情形下，一個凸多面體上最多有ｎ的４次方個最短序列，而就算這項猜測錯誤，在
實際上我們的方法也會比Sharir的方法快。
|