Computing the link center of a simple polygon (Q1104086)

The link center of a simple polygon \({\mathfrak P}\) is the set of points x inside \({\mathfrak P}\) at which the maximal link-distance from x to any other point in \({\mathfrak P}\) is minimized. Here the link distance between two points x, y inside \({\mathfrak P}\) is defined to be the smallest number of straight edges in a polygonal path inside \({\mathfrak P}\) connecting x to y. We prove several geometric properties of the link center and present an algorithm that calculates this set in time \(O(n^ 2)\), where n is the number of sides of \({\mathfrak P}\). We also give an O(n log n) algorithm for finding an approximate link center, that is, a point x such that the maximal link distance from x to any point in \({\mathfrak P}\) is at most one more than the value attained from the true link center.