Computing Geodesic Furthest Neighbors in Simple Polygons
Computing Geodesic Furthest Neighbors in Simple Polygons
复制标题
计算简单多边形中的测地线最远邻居
DOI：
10.1016/0022-0000(89)90045-7
复制
发表时间：
1989
期刊：
影响因子：
--
通讯作者：
S. Suri
中科院分区：
文献类型：
--
作者：
S. Suri
给出了一个计算简单多边形所有顶点的测地线最远邻点的算法，其中测地线表示多边形两点之间的距离定义为连接多边形内两点的欧氏最短路径的长度。算法的时间复杂度为O（nlogn），空间复杂度为O（n），n为多边形的顶点数。作为推论，多边形的测地直径也可以在相同的时间和空间范围内计算。
An algorithm is presented for computing geodesic furthest neighbors for all the vertices of a simple polygon, where geodesic denotes the fact that distance between two points of the polygon is defined as the length of an Euclidean shortest path connecting them within the polygon. The algorithm runs inO(nlogn) time and usesO(n) space;nbeing the number of vertices of the polygon. As a corollary, the geodesic diameter of the polygon also can be computed within, the same time and space bounds.