THE ROBBER ROUTE PROBLEM

被引：7

作者：

NTAFOS, S

机构：

[1] Computer Science Program, The University of Texas at Dallas, Richardson

来源：

INFORMATION PROCESSING LETTERS | 1990年 / 34卷 / 02期

关键词：

Computational geometry; visibility; watchman routes;

D O I：

10.1016/0020-0190(90)90137-M

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

We are given a polygon P together with a point x on the boundary of P, a set S of edges of P (the sights), and a set T of points in P (the threats). The robber route (or {{S, T}-route) problem is to find a shortest route (if one exists) from x to x and such that every point in S is visible from some point along the route while the route is not visible to any of the points in T. We present necessary and sufficient conditions for the existence of a robber route and results on the complexity of the robber route problem and its relationship to the watchman route problem. © 1990.

引用

页码：59 / 63

页数：5

共 9 条

[1]

Chin W.P., 1987, C NUMERANTIUM, V58, P257

[2] OPTIMUM WATCHMAN ROUTES [J].

CHIN, WP ;

NTAFOS, S .

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

[3]

CHIN WP, IN PRESS DISCRETE CO

[4]

EDELSBRUNNER H., 1983, ADV COMPUTING RES, V1, P35

[5]

GEWALI L, 1988, 4TH P ACM S COMP GEO, P266

[6]

Guibas L., 1986, 2ND P ANN ACM S COMP, P1, DOI DOI 10.1145/10515.10516

[7]

MITCHELL JSB, 1987, 3RD P ACM S COMP GEO, P30

[8]

Orourke J., 1987, ART GALLERY THEOREMS, V57

[9]

SURI S, 1986, 2ND P ACM S COMP GEO, P14

← 1 →