连结距离

在计算几何中，两点间的连结距离（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]