TY - JOUR
T1 - Computing external farthest neighbors for a simple polygon
AU - Agarwal, Pankaj K.
AU - Aggarwal, Alok
AU - Aronov, Boris
AU - Kosaraju, S. Rao
AU - Schieber, Baruch
AU - Suri, Subhash
N1 - Funding Information:
* Work on this paper by the first author has been supported by Office of Naval Research Grant N00014-87-K-0129, by National Science Foundation Grant No. NSF-DCR-83-20085, by grants from the Digital Equipment Corporation, and the IBM Corporation. Work on this paper by the third author has been supported by an AT&T Bell Laboratories PhD Scholarship. Work by the fourth author has been supported by NSF Grant CCR-8804284.
PY - 1991/4/15
Y1 - 1991/4/15
N2 - Let P be (the boundary of) a simple polygon with n vertices. For a vertex p of P, let φ{symbol}(p) be the set of points on P that are farthest from p, where the distance between two points is the length of the (Euclidean) shortest path that connects them without intersecting the interior of P. In this paper, we present an O(n log n) algorithm to compute a member of φ{symbol}(p) for every vertex p of P. As a corollary, the external diameter of P can also be computed in the same time.
AB - Let P be (the boundary of) a simple polygon with n vertices. For a vertex p of P, let φ{symbol}(p) be the set of points on P that are farthest from p, where the distance between two points is the length of the (Euclidean) shortest path that connects them without intersecting the interior of P. In this paper, we present an O(n log n) algorithm to compute a member of φ{symbol}(p) for every vertex p of P. As a corollary, the external diameter of P can also be computed in the same time.
UR - http://www.scopus.com/inward/record.url?scp=4043153839&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=4043153839&partnerID=8YFLogxK
U2 - 10.1016/0166-218X(91)90063-3
DO - 10.1016/0166-218X(91)90063-3
M3 - Article
AN - SCOPUS:4043153839
SN - 0166-218X
VL - 31
SP - 97
EP - 111
JO - Discrete Applied Mathematics
JF - Discrete Applied Mathematics
IS - 2
ER -