連結距離

在计算几何中，兩點間的連結距離（link distance）是指多邊形內以兩點為端點的任意折線之最小線段數。 多邊形的最大連結距離稱為該多邊形的連結直徑（link diameter）。[1]

簡單多邊形的連結直徑可以在O(n log n)時間內完成計算。[2]

定義

多邊形內兩點的連結距離定義為：

• 在多邊形P內部兩點x與y的連結距離可以表示為d_L(x,y)[1]。
• 則多邊形P的連結距離d_L(x,y)為在點x與點y之間繪製保持在多邊形P內部的折線（連續線段鏈），且這些線段不與邊界相交[1]，也都不會超出多邊形P的範圍，即不跑到多邊形P的外部；在滿足這個條件下，能以最少線段構成折線連接這兩點的折線線段數量即為d_L(x,y)的值[1]。
• 也就是說，如果兩點之間能完全在多邊形內部以一條直線段連接，則該兩點的連結距離為1。[1]

例如：

• 凸多邊形的任兩點連結距離必定為1，因為凸多邊形內任兩點都可以直接被單一線段連接[1]（連結距離考慮的是最小數量）
• 馬蹄形則有可能出現3或以上的連結距離，因為若選取的兩點位於馬蹄形的極端兩側，則需要例如ㄇ字形的折線來連接兩點。

多邊形的連結直徑定義為：

• 在多邊形內任取兩點評估其連結距離，其連結距離的最大值即為多邊形的連結直徑。[3]
• 兩點是任取兩點，因此需要考慮到極端情況。

例子

若多邊形的連結直徑為1，則他是凸多邊形，反之亦然。每個星狀多邊形的的連結直徑最多為2[4][5]：在星狀多邊形中可以透過在其星狀核內部彎曲一次來完成兩點連接。然而連結直徑為2的多邊形並不一定都是星狀多邊形，因為也存在有孔洞的多邊形，其連結直徑為2。此外，亦存在連結直徑4或5或以上的幾何圖形。[6]

參見

• 计算几何

參考文獻

1. Bose, Prosenjit and Toussaint, Godfried. Computing the constrained Euclidean, geodesic and link centre of a simple polygon with applications. Proceedings of CG International'96 (IEEE). 1996: 102–111. 
2. Suri, Subhash. On some link distance problems in a simple polygon. IEEE transactions on Robotics and Automation (IEEE). 1990, 6 (1): 108–113. 
3. Alsuwaiyel, Muhammed H and Lee, DT. Minimal link visibility paths inside a simple polygon. Computational Geometry (Elsevier). 1993, 3 (1): 1–25 [2023-11-26]. （原始内容存档于2023-11-27）. 
4. Aichholzer, Oswin and Aurenhammer, Franz and Hurtado Díaz, Fernando Alfredo and Ramos, Pedro A and Urrutia, J. Two-convex polygons. 25th European Workshop on Computational Geometry (Université Libre de Bruxelles). 2009: 117–120 [2023-11-26]. （原始内容存档于2022-07-05）. 
5. R. MajdNia. Extentions of algorithms for minimum bends geometric embedding of trees onto the points inside polygons (Master thesis论文). Computer engineering and IT dep., Amirkabir University of Tech. 2012-02. 
6. Bose, Prosenjit and Toussaint, Godfried. Geometric and computational aspects of manufacturing processes. Computers & graphics (Elsevier). 1994, 18 (4): 487–497 [2023-11-26]. （原始内容存档于2023-11-26）. 

延伸閱讀

• Maheshwari, Anil; Sack, Jörg-Rüdiger; Djidjev, Hristo N., Link distance problems, Handbook of Computational Geometry, North-Holland, Amsterdam: 519–558, 2000, MR 1746684, doi:10.1016/B978-044482537-7/50013-9