Title: Two-Guard Walkability of Simple Polygons L. H. Tseng Department of Applied Mathematics Feng Chia University Taichung 407, TAIWAN lhtseng@math.fcu.edu.tw P. Heffernan The Prudential Insurance Company of America 213 Washington St., Newark, NJ 07102-2992 heff@email.njin.net D.T. Lee Department of Electrical and Computer Engineering Northwestern University Evanston, IL, 60208 USA dtlee@ece.nwu.edu Abstract: A pair of points $s$ and $g$ on the boundary of a simple polygon $P$ admits a walk if two guards can simultaneously walk along the two boundary chains of $P$ from $s$ to $g$ such that they are always visible to each other. The walk is a counter-walk if one guard moves from $s$ to $g$ while the other moves from $g$ to $s$ in the same direction along the boundary and they are always visible to each other. The counter-walk is straight if no backtracking is necessary during the counter-walk. In this paper we show that, given a polygon with $n$ vertices, to test if there exists $(s, g)$ that admits a (straight) \mbox{(counter-)walk} can be solved in time $O(n \log n)$ and in linear space. Also we compute all $(s,g)$'s that admit a (straight) walk in $O(n \log n)$ time and all vertex pairs that admit a (straight) counter-walk in $O(n\log n + m)$, where $m$ is $O(n^{2})$. Keywords: Visibility, watchman routes, motion planning, simple polygon, circular-arc graph. Int' J. Computational Geometry & Applications, (8,1) Feb. 1998, 85-116.