Clearing a polygon with two 1-searchers

Borislav H. Simov, Giora Slutzki, Steven M. Lavalle

Research output: Contribution to journalArticle


We present an algorithm for a pair of pursuers, each with one flashlight, searching for an unpredictable, moving target in a 2D environment (simple polygon). Given a polygon with n edges and m concave regions, the algorithm decides in time O(n2 + nm2 + m4) whether the polygon can be cleared by the two 1-searchers, and if so, constructs a search schedule. The pursuers are allowed to move on the boundary and in the interior of the polygon. They are not required to maintain mutual visibility throughout the pursuit.

Original languageEnglish (US)
Pages (from-to)59-92
Number of pages34
JournalInternational Journal of Computational Geometry and Applications
Issue number1
StatePublished - Feb 1 2009



  • Motion planning
  • Pursuit-evasion
  • Robotics
  • Sensing
  • Visibility

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Computational Theory and Mathematics
  • Computational Mathematics
  • Applied Mathematics

Cite this