AN INCREMENTAL ALGORITHM FOR CONSTRUCTING SHORTEST WATCHMAN ROUTES

被引：30

作者：

Tan, Xuehou ^{[1
]}

Hirata, Tomio ^{[2
]}

Inagaki, Yasuyoshi ^{[2
]}

机构：

[1] Tokai Univ, Sch High Technol Human Welf, Numazu 41003, Japan

[2] Nagoya Univ, Fac Engn, Chikusa Ku, Nagoya, Aichi 464, Japan

来源：

INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS | 1993年 / 3卷 / 04期

关键词：

Algorithms; computational geometry; watchman routes; essential cuts;

D O I：

10.1142/S0218195993000233

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

The problem of finding the shortest watchman route in a simple polygon P through a point s on its boundary is considered. A route is a watchman route if every point inside P can be seen from at least one point along the route. We present an incremental algorithm that constructs the shortest watchman route in O(n(3)) time for a simple polygon with n edges. This improves the previous O(n(4)) bound.

引用

页码：351 / 365

页数：15

共 6 条

[1]

Chazelle B., 1990, Proceedings. 31st Annual Symposium on Foundations of Computer Science (Cat. No.90CH2925-6), P220, DOI 10.1109/FSCS.1990.89541

[2] OPTIMUM WATCHMAN ROUTES [J].

CHIN, WP ;

NTAFOS, S .

INFORMATION PROCESSING LETTERS, 1988, 28 (01) :39-44

[3] SHORTEST WATCHMAN ROUTES IN SIMPLE POLYGONS [J].

CHIN, WP ;

NTAFOS, S .

DISCRETE & COMPUTATIONAL GEOMETRY, 1991, 6 (01) :9-31

[4] 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

[5] THE ROBBER ROUTE PROBLEM [J].

NTAFOS, S .

INFORMATION PROCESSING LETTERS, 1990, 34 (02) :59-63

[6]

Tan X., 1993, CONSTRUCTING S UNPUB

← 1 →