摘要：The rectilinear link distance between two points inside a simple rectilinear polygon P is defined to be the minimum number of edges of a path consisting of axis-parallel segments lying inside P. The link diameter of P is the maximum link distance between two points of P. We present an O(n) time algorithm for computing the link diameter of a simple rectilinear polygon P, where n is the number of vertices of P. This improves the previous O(nlogn) time algorithm.
