Computing the link center of a simple polygon

W. Lenhart, R. Pollack, J. Sack, R. Seidel, M. Sharir, S. Suri, G. Toussaint, S. Whitesides, C. Yap

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)281-293
Number of pages13
JournalDiscrete & Computational Geometry
Issue number1
StatePublished - Dec 1988

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics


Dive into the research topics of 'Computing the link center of a simple polygon'. Together they form a unique fingerprint.

Cite this