Computing external farthest neighbors for a simple polygon

Computing external farthest neighbors for a simple polygon

0.00 Avg rating0 Votes
Article ID: iaor19912045
Country: Netherlands
Volume: 31
Issue: 2
Start Page Number: 97
End Page Number: 111
Publication Date: Apr 1991
Journal: Discrete Applied Mathematics
Authors: , , , , ,
Abstract:

Let 𝒫 be (the boundary of) a simple polygon with n vertices. For a vertex p of 𝒫, let ø(p) be the set of points on 𝒫 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 𝒫. In this paper, the authors present an O(nlogn) algorithm to compute a member of ø(p) for every vertex p of 𝒫. As a corollary, the external diameter of 𝒫 can also be computed in the same time.

Reviews

Required fields are marked *. Your email address will not be published.