The optimization version of the traditional Art Gallery problem asks for a minimum set of point guards that can be placed within a polygon, such that any point in the polygon is visible from at least one guard.

Has there been a study of guarding a given set of paths (e.g. piecewise linear) that lie within the polygon (instead of guarding the entire polygon) with minimum number of guards? The closest related works I found are

  • Chapter 4 from Urrutia's book covers a set of problems about "illuminating" a set of lines with floodlights. This is fundamentally different since the lines themselves act as obstacles, whereas I'm interested in the version where the paths can be thought of as transparent and only the polygon boundary affects the visibility.
  • Minimum Line Cover Problem which asks for the minimum set of points to cover a set of lines (or vice versa) lying in the plane. There is no notion of visibility.

If there is a finite set of candidate guard locations, then general set cover techniques can be applied to yield a log approximation. However, I'm wondering if there has been a systematic study of this variant of the problem.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.