Abstract
最近在計算機幾何學的研究，已經開始注意到非歐氏幾何學的距離觀念，其中鏈結距離（link distance ）和測地線距離（geodesic distance ）是最引起注意的兩個主題。所謂兩點的鏈結距離是指聯結兩點的所有路徑中，直線最少的個數，此路徑則稱為該兩點的鏈結路徑（link path ）。鏈結距離有它多方面的實用性，例如在機器人的路徑規劃中，對機器人而言，直線移動是件容易的事，但轉彎則需較大的花費，所以當機器人要從某一位置移動到另一位置時，它會選擇走該兩點的鏈結路徑。另外一個我們所探討的主題是 測地線距離，所謂兩點的測地線距離是指聯結兩點的所有路徑中，該路徑直線段長度總和最少者，此路徑我們稱為該兩點的測地線路徑（geode-sic path），為了避開環境中不可超越的障礙物和花費代價最少，測地線路徑是最佳的選擇。圍繞在這兩種新的距離觀念上，我們可以賦予一些基本的名詞敨多新的概念，如直徑（diameter），半徑（radius），中心（center）等等。在這篇論文中我們要探討一個特別的多邊形稱為〞弱可見性多邊形〞（weakly visible polygon），並且針對這一種多邊形找到幾個線性時間的演算法，來解所謂的三角化問題（triangu-lation），鏈結中心（link center ）和鏈結半徑（link radius ）問題，另外我們也提出一個０（klogn+n ）的演算法來解測地線直徑（geodesic diameter ）問題，這裡的 n是多邊形的頂點個數，k 則是凸點個數。最後我們要介紹一個新的直徑問題：在一個有n 個頂點的一般多邊形內部撒下m 個點，求這m 個點的測地線直徑。我們找到三個方法，其中第三個方法有最小的複雜度０（nloglogn+mlogn+mlogm）。