請用此 Handle URI 來引用此文件: http://hdl.handle.net/11455/38286
標題: Two Guard Walkability of Simple Polygons
作者: L.H.Tseng
D.T.Lee
P.Heffernan
關鍵字: Visibility
watchman routes
motion planning
simple polygon
circular-arc graph
摘要: 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) (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(n2). Read More: http://www.worldscientific.com/doi/abs/10.1142/S0218195998000060
URI: http://hdl.handle.net/11455/38286
顯示於類別:資訊科學與工程學系所

文件中的檔案:
沒有與此文件相關的檔案。
顯示文件完整紀錄
 
 
Citations:


在 DSpace 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。