Hide-and-Seek: A Linear Time Algorithm for Polygon Walk Problems
文献类型：会议论文
| 作者 | Atlas F. Cook IV; Chenglin Fan; Jun Luo |
| 出版日期 | 2011 |
| 会议名称 | Proceeding TAMC'11 Proceedings of the 8th annual conference on Theory and applications of models of computation |
| 英文摘要 | Jack and Jill want to play hide-and-seek on the boundary of a simplepolygon. Given arbitrary paths for the two children along this boundary, ourgoal is to determine whether Jack can walk along his path without ever beingseen by Jill. To solve this problem, we use a linear-sized skeleton invisibility diagramto implicitly represent invisibility information between pairs of points onthe boundary of the simple polygon. This structure has additional applications forany polygon walk problem where one entity wishes to remain hidden throughouta traversal of some path. We also show how Jack can avoid being seen not just by one moving child but by an arbitrary number of moving children. |
| 收录类别 | 其他 |
| 语种 | 英语 |
| 源URL | [http://ir.siat.ac.cn:8080/handle/172644/3604]  |
| 专题 | 深圳先进技术研究院_数字所 |
| 作者单位 | 2011 |
| 推荐引用方式 GB/T 7714 | Atlas F. Cook IV,Chenglin Fan,Jun Luo. Hide-and-Seek: A Linear Time Algorithm for Polygon Walk Problems[C]. 见:Proceeding TAMC'11 Proceedings of the 8th annual conference on Theory and applications of models of computation. |
入库方式： OAI收割
来源：深圳先进技术研究院
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。