Computing the link center of a simple polygon

Abstract

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. Here the link distance between two points x, y inside P is defined to be 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 O(n2), where n is the number of sides of 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 P is at most one more than the value attained from the true link center. © 1988 Springer-Verlag New York Inc.