TY - GEN
T1 - Computing the link center of a simple polygon
AU - Lenhart, W.
AU - Pollack, R.
AU - Sack, J.
AU - Seidel, R.
AU - Shari, M.
AU - Suri, S.
AU - Toussaint, G.
AU - Whitesides, S.
AU - Yap, C.
N1 - Funding Information:
Acknowledgements: Work on this paper by the second author has been supported by National Science Foundation Grant DMS-8501947. Work by the third author was supported by the Canadian National Science and Engineering Research Council, grant A0332. Work by the fifth author has been supported by Office of Naval Research Grant N00014-82-K-0381, National Science Foundation Grant No. NSF-DCR-83-20085, and by grants from the Digital Equipment Corporation, and the IBM Corporation. Work by the seventh author has been supported by a Killam Senior Research Fellowship from the Canada Council, and work by the ninth author was supported by the National Science Foundation Grants DCR-84-01898 and DCR-84-01633. Part of the work on this paper has been carried out at the Workshop on Movable Separability of Sets at the Bellairs Research Institute of McGill University, Barbados, February 1986. Further acknowledgements can be obtained from the tenth author upon request.
Funding Information:
Work on this paper by the second author has been supported by National Science Foundation Grant DMS-8501947. Work by the third author was supported by the Canadian National Science and Engineering Research Council, grant A0332. Work by the fifth author has been supported by Office of Naval Research Grant N00014-82-K-0381, National Science Foundation Grant No. NSF-DCR-83-20085, and by grants from the Digital Equipment Corporation, and the IBM Corporation. Work by the seventh author has been supported by a Killam Senior Research Fellowship from the Canada Council, and work by the ninth author was supported by the National Science Foundation Grants DCR-84-01898 and DCR-84-01633. Part of the work on this paper has been carried out at the Workshop on Movable Separability of Sets at the Bellairs Research Institute of McGill University, Barbados, February 1986. Further acknowledgements can be obtained from the tenth author upon request.
Publisher Copyright:
© 1987 ACM.
PY - 1987/10/1
Y1 - 1987/10/1
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85036466524&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85036466524&partnerID=8YFLogxK
U2 - 10.1145/41958.41959
DO - 10.1145/41958.41959
M3 - Conference contribution
AN - SCOPUS:85036466524
T3 - Proceedings of the 3rd Annual Symposium on Computational Geometry, SCG 1987
SP - 1
EP - 10
BT - Proceedings of the 3rd Annual Symposium on Computational Geometry, SCG 1987
A2 - Soule, D.
PB - Association for Computing Machinery, Inc
T2 - 3rd Annual Symposium on Computational Geometry, SCG 1987
Y2 - 8 June 1987 through 10 June 1987
ER -