No label defined (Q4945513)

The study of link distance problems is motivated by applications in computer graphics, geographical information systems, robotics, image processing, VLSI, etc. The link distance, defined with respect to a planar region \(R\), sets the distance between a pair of points \((s, t)\) in \(R\) to be the minimum number of line segments needed to construct a path in \(R\) that connects \(s\) to \(t\). A path connecting \(s\) and \(t\) of length equal to the link distance between \(s\) and \(t\) is called a minimum link path. The paper gives a clearly written systematic overview about various link distance problems set in simple polygons, rectilinear polygons, and polygonal regions with holes. Sections 2 and 3 deal with sequential and parallel algorithms for link distance problems in Euclidean and rectilinear metric spaces, respectively. Section 4 deals with various applications and extensions of link distance problems. For the entire collection see [Zbl 0930.65001].