An algorithm for searching a polygonal region with a flashlight

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

Research output: Contribution to journalArticlepeer-review

Abstract

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
Volume12
Issue number1-2
DOIs
StatePublished - 2002

Keywords

  • 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 'An algorithm for searching a polygonal region with a flashlight'. Together they form a unique fingerprint.

Cite this