リンク距離

計算幾何学において、多角形内の2点間のリンク距離とは、その2点を端点とする多角形連鎖の線分の最小数です。多角形のリンク直径とは、その多角形内の任意の2点間の最大リンク距離です

多角形が凸多角形となるのは、そのリンク直径が1である場合に限ります。すべての星型多角形のリンク直径は最大で2です。つまり、2点間の接続は、多角形の核の内部で1回折れ曲がる多角形鎖で結ばれる可能性があります。ただし、この性質は星型多角形には当てはまりません。リンク直径が2である 穴のある多角形も存在するからです。

参考文献

• Maheshwari, Anil; Sack, Jörg-Rüdiger ; Djidjev, Hristo N. (2000)、「リンク距離問題」、Handbook of Computational Geometry、North-Holland、アムステルダム、pp.  519– 558、doi :10.1016/B978-044482537-7/50013-9、ISBN 978-0-444-82537-7、MR  1746684。