连结距离

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

参见

• 计算几何