Computing external farthest neighbors for a simple polygon

Published

Journal Article

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. © 1991.

Full Text

Duke Authors

Cited Authors

  • Agarwal, PK; Aggarwal, A; Aronov, B; Kosaraju, SR; Schieber, B; Suri, S

Published Date

  • April 15, 1991

Published In

Volume / Issue

  • 31 / 2

Start / End Page

  • 97 - 111

International Standard Serial Number (ISSN)

  • 0166-218X

Digital Object Identifier (DOI)

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

Citation Source

  • Scopus