Rectilinear link diameter and radius in a rectilinear polygonal domain (Q827313)

Diameters and radii are commonly used characteristics of metric spaces. Much research has been devoted towards finding efficient algorithms to compute the diameter and radius for various types of sets and metrics. In computational geometry, one of the most well-studied and natural metric spaces is a polygon in the plane. This paper focuses on the computation of the diameter and the radius of a rectilinear polygon, possibly with holes under the rectilinear link distance. Intuitively, this metric measures the minimum number of links (segments) required in any rectilinear path connecting two points in the domain, where rectilinearity indicates that we are restricted to horizontal and vertical segments only. The interest was motivated by potential robotics applications but the proposed algorithms can be applied not only there.