COMPUTING EXTERNAL FARTHEST NEIGHBORS FOR A SIMPLE POLYGON

被引：6

作者：

AGARWAL, PK

AGGARWAL, A

ARONOV, B

KOSARAJU, SR

SCHIEBER, B

SURI, S

机构：

[1] IBM CORP,DIV RES,YORKTOWN HTS,NY 10598

[2] JOHNS HOPKINS UNIV,BALTIMORE,MD 21218

[3] BELL COMMUN RES INC,MORRISTOWN,NJ 07960

来源：

DISCRETE APPLIED MATHEMATICS | 1991年 / 31卷 / 02期

基金：

美国国家科学基金会;

关键词：

D O I：

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

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

Let P be (the boundary of) a simple polygon with n vertices. For For a vertex p of P, let phi(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 phi(p) for every vertex p of P. As a corollary, the external diameter of P can also be computed in the same time.

引用

收藏

页码：97 / 111

页数：15

相关论文

共 9 条

[1] DEQUES WITH HEAP ORDER. [J].

Gajewska, Hania ;

Tarjan, Robert E. .

Information Processing Letters, 1986, 22 (04) :197-200

[2] FINDING THE CONVEX-HULL OF A SIMPLE POLYGON [J].

GRAHAM, RL ;

YAO, FF .

JOURNAL OF ALGORITHMS, 1983, 4 (04) :324-331

[3] LINEAR-TIME ALGORITHMS FOR VISIBILITY AND SHORTEST-PATH PROBLEMS INSIDE TRIANGULATED SIMPLE POLYGONS [J].

GUIBAS, L ;

HERSHBERGER, J ;

LEVEN, D ;

SHARIR, M ;

TARJAN, RE .

ALGORITHMICA, 1987, 2 (02) :209-233

[4] OPTIMAL SHORTEST-PATH QUERIES IN A SIMPLE POLYGON [J].

GUIBAS, LJ ;

HERSHBERGER, J .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1989, 39 (02) :126-152

[5] EUCLIDEAN SHORTEST PATHS IN THE PRESENCE OF RECTILINEAR BARRIERS [J].

LEE, DT ;

PREPARATA, FP .

NETWORKS, 1984, 14 (03) :393-410

[6] COMPUTING THE GEODESIC CENTER OF A SIMPLE POLYGON [J].

POLLACK, R ;

SHARIR, M ;

ROTE, G .

DISCRETE & COMPUTATIONAL GEOMETRY, 1989, 4 (06) :611-626

[7] COMPUTING THE EXTERNAL GEODESIC DIAMETER OF A SIMPLE POLYGON [J].

SAMUEL, D ;

TOUSSAINT, GT .

COMPUTING, 1990, 44 (01) :1-19

[8] WORST-CASE DATA-STRUCTURES FOR THE PRIORITY QUEUE WITH ATTRITION [J].

SUNDAR, R .

INFORMATION PROCESSING LETTERS, 1989, 31 (02) :69-75

[9] COMPUTING GEODESIC FURTHEST NEIGHBORS IN SIMPLE POLYGONS [J].

SURI, S .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1989, 39 (02) :220-235