Computing the link center of a simple polygon
William Lenhart, Richard M. Pollack, Jörg-Rüdiger Sack, Raimund Seidel, Micha Sharir · 1987
The link center of a simple polygon P is the set of points x inside P at which the maximal link-distance from x to any other point in P is minimized, where the link distance between two points x, y inside P is defined as the smallest number of straight edges in a polygonal path inside P connecting x to y. We prove several geometric properties of the link center and present an algorithm that calculates this set in time Ο (n2), where n is the number of sides of P. We also give an Ο(n log n) algorithm for finding a point x in an approximate link center, namely the maximal link distance from x to any point in P is at most one more than the value attained from the link center.