Partial Searchlight Scheduling is Strongly PSPACE-complete

Details Partial Searchlight Scheduling is Strongly PSPACE-complete Partial Searchlight Scheduling is Strongly PSPACE-complete

2012-01-10

arxiv.org/abs/1201.2097v2

Computer Science

Computational Geometry

4 pages, 6 figures

Scientific paper

The problem of searching a polygonal region for an unpredictably moving intruder by a set of stationary guards, each carrying an orientable laser, is known as the Searchlight Scheduling Problem. Determining the complexity of deciding if the entire area can be searched is a long-standing open problem. Recently, the author introduced the Partial Searchlight Scheduling Problem, in which only a given subregion of the environment has to be searched, and proved that its 3-dimensional decision version is PSPACE-hard, even when restricted to orthogonal polyhedra. Here we extend and refine this result, by proving that 2-dimensional Partial Searchlight Scheduling is strongly PSPACE-complete, both in general and restricted to orthogonal polygons in which the region to be searched is a rectangle.

Affiliated with

Also associated with

No associations

Rating

Partial Searchlight Scheduling is Strongly PSPACE-complete does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Partial Searchlight Scheduling is Strongly PSPACE-complete, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Partial Searchlight Scheduling is Strongly PSPACE-complete will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-463307