Computing external farthest neighbors for a simple polygon

Pankaj K. Agarwal; Alok Aggarwal; Boris Aronov; S. Rao Kosaraju; Baruch Schieber; Subhash Suri

doi:10.1016/0166-218X(91)90063-3

Computing external farthest neighbors for a simple polygon

Pankaj K. Agarwal, Alok Aggarwal, Boris Aronov, S. Rao Kosaraju, Baruch Schieber, Subhash Suri

Research output: Contribution to journal › Article › peer-review

7 Scopus citations

Abstract

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.

Original language	English (US)
Pages (from-to)	97-111
Number of pages	15
Journal	Discrete Applied Mathematics
Volume	31
Issue number	2
DOIs	https://doi.org/10.1016/0166-218X(91)90063-3
State	Published - Apr 15 1991
Externally published	Yes

All Science Journal Classification (ASJC) codes

Discrete Mathematics and Combinatorics
Applied Mathematics

Access to Document

10.1016/0166-218X(91)90063-3

Cite this

@article{801dc08110234d419d679ecf58bf6896,

title = "Computing external farthest neighbors for a simple polygon",

abstract = "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.",

author = "Agarwal, {Pankaj K.} and Alok Aggarwal and Boris Aronov and Kosaraju, {S. Rao} and Baruch Schieber and Subhash Suri",

note = "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.",

year = "1991",

month = apr,

day = "15",

doi = "10.1016/0166-218X(91)90063-3",

language = "English (US)",

volume = "31",

pages = "97--111",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier B.V.",

number = "2",

}

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 -

Computing external farthest neighbors for a simple polygon

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this