An optimal algorithm for the two-guard problem
An optimal algorithm for the two-guard problem
复制标题
DOI：
10.1145/160985.161163
复制
发表时间：
1993-07
期刊：
影响因子：
--
通讯作者：
P. Heffernan
中科院分区：
文献类型：
--
作者：
P. Heffernan
在本文中，我们给出了两个版本的两个警卫问题的最优解。给定一个顶点为s和t的简单多边形P，直线行走问题询问我们是否可以将P上的两个点从s单调移动到t，一个顺时针，一个逆时针，使得这些点总是共同可见。在逆行走问题中，两个点都是顺时针移动的，一个从s到t，另一个从t到s。我们提供（n）建设性的算法，这两个问题。我们得到我们的结果，通过检查的结构上的两个点的运动的限制，并采用最短路径和最短路径树的属性。
In this paper we give optimal solutions for two versions of the two-guard problem. Given a simple polygon P with vertices s and t, the straight walk problem asks whether we can move two points monotonically on P from s to t, one clockwise and one counterclockwise, such that the points are always co-visible. In the counter walk problem, both points move clockwise, one from s to t and the other from t to s. We provide &THgr;(n) constructive algorithms for both problems. We obtain our results by examining the structure of the restrictions placed on the motion of the two points, and by employing properties of shortest paths and shortest path trees.