Clearing a polygon with two 1-searchers

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

Research output: Contribution to journalArticlepeer-review


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 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

Fingerprint Dive into the research topics of 'Clearing a polygon with two 1-searchers'. Together they form a unique fingerprint.

Cite this