SCIENCE@home

Partial Searchlight Scheduling is Strongly PSPACE-complete

G. Viglietta

Published 2012 in Canadian Conference on Computational Geometry

ABSTRACT

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 computational complexity of deciding if the polygon can be searched by a given set of guards is a long-standing open problem. Here we propose a generalization called the Partial Searchlight Scheduling Problem, in which only a given subregion of the environment has to be searched, as opposed to the entire area. We prove that the corresponding decision problem is strongly PSPACE-complete, both in general and restricted to orthogonal polygons where the region to be searched is a rectangle. Our technique is to reduce from the "edge-to-edge" problem for nondeterministic constraint logic machines, after showing that the computational power of such machines does not change if we allow "asynchronous" edge reversals (as opposed to "sequential").

PUBLICATION RECORD

  • Publication year

    2012

  • Venue

    Canadian Conference on Computational Geometry

  • Publication date

    2012-01-10

  • Fields of study

    Mathematics, Computer Science

  • Identifiers
    arXiv 1201.2097
  • External record

    Open on Semantic Scholar

  • Source metadata

    Semantic Scholar

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-8 of 8 references · Page 1 of 1

CITED BY