ScholarLens Back to search
2009•International Journal of Computational Geometry & ApplicationsRequires access

CLEARING A POLYGON WITH TWO 1-SEARCHERS

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

Open publisher page 18 citations

Abstract

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.

About this research paper

What this paper is about

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.

Why it matters

OpenAlex reports 18 citations for this work. Citation counts describe recorded attention and do not establish research quality.

Key contribution

A contribution statement is not available in the OpenAlex record.

Method / approach

Method details are not available in the OpenAlex metadata.

Main findings

Findings are not separately available in the OpenAlex metadata.

Limitations

Limitations are not available in the OpenAlex metadata.

Applications

Application details are not available in the OpenAlex metadata.

Available abstract

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.

Key concepts: Visibility polygon, Polygon (computer graphics), Simple polygon, Polygon covering, Star-shaped polygon, Combinatorics, Visibility, Rectilinear polygon

Related papers

Related paper 1Related paper 2Related paper 3
Back to paper searchBrowse research topicsOriginal source
CLEARING A POLYGON WITH TWO 1-SEARCHERS — Research Paper | ScholarLens