An algorithm for searching a polygonal region with a flashlight

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

Research output: Contribution to journalArticlepeer-review


We present an algorithm for a single pursuer with one flashlight searching for an unpredictable, moving target in a 2D environment. The algorithm decides whether a simple polygon with n edges and m concave regions can be cleared by the pursuer, and if so, constructs a search schedule of length O(m) in time O(m2 + m log n + n). The key ideas in this algorithm include a representation called "visibility obstruction diagram" and its "skeleton": a combinatorial decomposition based on a number of critical visibility events. An implementation is presented along with a computed example.

Original languageEnglish (US)
Pages (from-to)87-113
Number of pages27
JournalInternational Journal of Computational Geometry and Applications
Issue number1-2
StatePublished - 2002


  • 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


Dive into the research topics of 'An algorithm for searching a polygonal region with a flashlight'. Together they form a unique fingerprint.

Cite this