An O(n log n) ALGORITHM FOR FINDING A SHORTEST CENTRAL LINK SEGMENT
Lyudmil Aleksandrov, Hristo N. Djidjev, Jörg-Rüdiger Sack · International Journal of Computational Geometry & Applications · 2000
A central link segment of a simple n-vertex polygon P is a segment s inside P that minimizes the quantity max x∈P min y∈s d L (x,y), where d L (x,y) is the link distance between points x and y of P. In this paper we present an O (n log n) algorithm for finding a central link segment of P. This generalizes previous results for finding an edge or a segment of P from which P is visible. Moreover, in the same time bound, our algorithm finds a central link segment of minimum length. Constructing a central link segment has applications to the problems of finding an optimal robot placement in a simply connected polygonal region and determining the minimum value k for which a given polygon is k-visible from some segment.