連結距離

在計算幾何中，兩點間的連結距離（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.0 ^1.1 ^1.2 ^1.3 ^1.4 ^1.5 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.
^ Suri, Subhash. On some link distance problems in a simple polygon. IEEE transactions on Robotics and Automation (IEEE). 1990, 6 (1): 108–113.
^ 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）.
^ 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）.
^ 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.
^ 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

[inproceedings_bose1996computing-1] 1.0 ^1.1 ^1.2 ^1.3 ^1.4 ^1.5 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.

[article_suri1990some-2] Suri, Subhash. On some link distance problems in a simple polygon. IEEE transactions on Robotics and Automation (IEEE). 1990, 6 (1): 108–113.

[article_alsuwaiyel1993minimal-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）.

[inproceedings_aichholzer2009two-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.

[article_bose1994geometric-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）.

[1]

[2]

[3]

[4]

[5]

[6]