期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

Searching a Polygonal Region by a Boundary Searcher 被引量：1

Searching a Polygonal Region by a Boundary Searcher
原文传递
导出
摘要 This paper considers the problem of planning the motion of a searcher in a polygonal region to eventually ＂see＂ an intruder that is unpredictable and capable of moving arbitrarily fast. A searcher is called the boundary searcher if he continuously moves on the polygon boundary and can see only along the rays of the flashlights he holds at a time. We present necessary and sufficient conditions for an n-sided polygon to be searchable by a boundary searcher. Based on our characterization, the equivalence of the ability of the searchers having only one flashlight and the one of the searchers having full 360° vision is simply established, and moreover, an optimal O（n） time and space algorithm for determining the searchability of simple polygons is obtained. We also give an O（n log n ＋ I） time algorithm for generating a search schedule if it exists, where I （〈 3n^2） is the number of search instructions reported. Our results improve upon the previously known O（n^2） time and space bounds. This paper considers the problem of planning the motion of a searcher in a polygonal region to eventually ＂see＂ an intruder that is unpredictable and capable of moving arbitrarily fast. A searcher is called the boundary searcher if he continuously moves on the polygon boundary and can see only along the rays of the flashlights he holds at a time. We present necessary and sufficient conditions for an n-sided polygon to be searchable by a boundary searcher. Based on our characterization, the equivalence of the ability of the searchers having only one flashlight and the one of the searchers having full 360° vision is simply established, and moreover, an optimal O（n） time and space algorithm for determining the searchability of simple polygons is obtained. We also give an O（n log n ＋ I） time algorithm for generating a search schedule if it exists, where I （〈 3n^2） is the number of search instructions reported. Our results improve upon the previously known O（n^2） time and space bounds.
作者 谭学厚
机构地区 School of High-Technology for Human Welfare.Tokai University
出处 《Journal of Computer Science & Technology》 SCIE EI CSCD 2009年第3期505-516,共12页 计算机科学技术学报（英文版）
关键词 computational geometry ROBOTICS VISIBILITY polygon search problem two-guard problem computational geometry, robotics, visibility, polygon search problem, two-guard problem
分类号 TN929.5 [电子电信—通信与信息系统]
  • 相关文献

参考文献1

二级参考文献21

  • 1Bhattacharya B K, Ghosh S K. Characterizing LR-visibility polygons and related problems. Comput. Geom. The. Appl., 2001, 18(1): 19-36.
  • 2Chazelle B, Guibas L. Visibility and intersection problem in plane geometry. Discrete Comput. Geom., 1989, 4(6): 551- 581.
  • 3Park S M, Lee J H, Chwa K Y. Characterization of rooms searchable by two guards. Lect. Notes Comput. Sci., 1969, Lee D T, Tseng S H (eds.), Springer-Verlag, 2000, pp.515-526.
  • 4Park S M, Lee J H, Chwa K Y. Visibility-based pursuitevasion in a polygonal region by a searcher. Leer. Notes Comput. Sci., 2076, Orejas F, Spirakis P G, Leeuwen J wn (eds.), Springer-Verlag, 2001, pp.456-468.
  • 5Suzuki I, Yamashita Y. Searching for mobile intruders in a polygonal region. SIAM J. Comp., 1992, 21(5): 863-888.
  • 6Crass D, Suzuki I, Yamashita Y. Searching for a mobile intruder in a corridor. Int. J. Comput. Geom. & Appl., 1995, 5(4): 397-412.
  • 7Suzuki I, Tazoe Y, Yamashita M, Kameda T. Searching a polygonal region from the boundary. Int. J. Comput. Geom. & Appl., 2001, 11(5): 529-553.
  • 8Efrat A, Guibas L J, Har-Peled S, Lin D C, Mitchell J S B, Murali T M. Sweeping simple polygons with a chain of guards. In Proc. ACM-SIAM Syrup. Discrete Algorithms, California, USA, 2000, pp.927-936.
  • 9Tan X. Searching a simple polygon by a k-searcher. Lect. Notes Comput. Sei., 1969, Lee D T, Tseng S -H (eds.), Springer-Verlag, 2000, pp.503-514.
  • 10Tan X. A characterization of polygonal regions searchable from the boundary. Leer. Notes Comput. Sei., 3330, Akiyama J, Baskoro E T, Kano M (eds.), Springer-Verlag, 2004, pp.200-215.

同被引文献10

  • 1SUZUKI I, YAMASHITA M. Searching for a mobile intvader in a polygonal region[ J]. SIAM Journal on Computing, !992, 21 (5) : 863-888.
  • 2PARK S M, LEE J H, CHWA K Y. A characterization of the class of polygons searchable by a 1-searcher. Technic,,d Report CS/TR-2000-160[ R]. Kaist: Korea Advanced Institute of Science and Technology, 2000.
  • 3TAN X. Searching a simple polygon by a k-searcher[ J ]. Lecture Notes in Computer Science, 2000, 1969/2000:275-319:.
  • 4LAVALLE S M, SIMOV B, SLUZKI G. An algorithm for searching a polygonal region with a flashlight[ J]. International Journal of Computational Geometry and Applications, 2002, 12(1/2) : 87-113.
  • 5TAN X. A characterization of polygonal regions searchable from the boundary [ J ]. Lecture Notes in Computer Science, 2005, 3330/2005 : 200-215.
  • 6KAMEDA T, ZHANG J Z, YAMASHITA M. Simple characterization of polygons searchable by 1-searcher : proceedings of the 18th Canadian conference on computational geometry, Kingston, Canada, 2006 [ C ]. Kingston: [ s. n. ] ,2006.
  • 7KAMEDA T, YAMASHITA M, SUZUKI I. On-line polygon search by a six-state boundary 1-searcher[ R]. Technical Report CMPT-TR 2003-07, Canada : Simon Fraser University, 2003.
  • 8SIMOV B, LAVALLE S M, SLUTZKI G. A complete pursuit-evasion algorithm for two pursuers using beam detection: procetings of IEEE international conference on robotics and automation, Washington D C, USA, 2002[C]. Washington D C: Is. n. ] ,2002.
  • 9DAS G, HEFFERNAN P J, NARASIMHAN G. LR-visibility in polygons [ J ]. Computational Geometry Theory and Applications, 1997, 7(1) : 37-57.
  • 10BHATrACHARYA B K, MUKHOPADHYAY A, NARASIMHAN G. Optimal algorithms for two-guard walkability of simple polygons[ C]//DEHNE F, SACK T R, TAMASSIA R. Algorithms and Data Structures, 7th International Workshop, WADS 2001, LNCS 2125. New York: Springer-Verlag, 2001,438-449.

引证文献1

Journal of Computer Science & Technology
2009年 第3期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部