Computing the link center of a simple polygon

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationProceedings of the 3rd Annual Symposium on Computational Geometry, SCG 1987
EditorsD. Soule
PublisherAssociation for Computing Machinery, Inc
Pages1-10
Number of pages10
ISBN (Electronic)0897912314, 9780897912310
DOIs
StatePublished - Oct 1 1987
Event3rd Annual Symposium on Computational Geometry, SCG 1987 - Waterloo, Canada
Duration: Jun 8 1987Jun 10 1987

Publication series

NameProceedings of the 3rd Annual Symposium on Computational Geometry, SCG 1987

Other

Other3rd Annual Symposium on Computational Geometry, SCG 1987
CountryCanada
CityWaterloo
Period6/8/876/10/87

ASJC Scopus subject areas

  • Computational Mathematics
  • Geometry and Topology

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

  • Cite this

    Lenhart, W., Pollack, R., Sack, J., Seidel, R., Shari, M., Suri, S., Toussaint, G., Whitesides, S., & Yap, C. (1987). Computing the link center of a simple polygon. In D. Soule (Ed.), Proceedings of the 3rd Annual Symposium on Computational Geometry, SCG 1987 (pp. 1-10). (Proceedings of the 3rd Annual Symposium on Computational Geometry, SCG 1987). Association for Computing Machinery, Inc. https://doi.org/10.1145/41958.41959