Computing the link center of a simple polygon
The link center of a simple polygon P is the set of points x inside P at which the maximal link-distancefrom x to any other point in P is minimized, where the link distance between two points x, y inside P isdefined as the smallest number of straight edges in a polygonal path inside P connecting x to y. We proveseveral geometric properties of the link center and present an algorithm that calculates this set in time0(n2), where n is the number of sides of P. We also give an 0 (n log n) algorithm for finding apoint 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.
|Conference||3rd Annual Symposium on Computational Geometry, SCG 1987|
Lenhart, W. (W.), Pollack, R. (R.), Sack, J.-R, Seidel, R. (R.), Shari, M. (M.), Suri, S. (S.), … Yap, C. (C.). (1987). Computing the link center of a simple polygon. In Proceedings of the 3rd Annual Symposium on Computational Geometry, SCG 1987 (pp. 1–10). doi:10.1145/41958.41959