Art Gallery Problem

number of guards

1

2

3

4

5

6

7

8

environment

movable obstacles

irregular

cubicle

Initialization timed out



How many omnidirectional cameras are needed to fully observe every part of a polygonal art gallery? Move the cameras by dragging the colored locators ("guards") to try to cover the polygon with the fewest guards.

Details

This Demonstration calculates the visible region for each guard. Up to eight guards can be used, and all are moveable.

Three different environments are provided. The "movable obstacles" environment contains a movable square and triangle.

References

[1] D.-T. Lee, "Proximity and Reachability in the Plane," Ph.D. dissertation, University of Illinois at Urbana-Champaign, Illinois, ProQuest Dissertations Publishing, 1978 7913526.

[2] Wikipedia. "Isovist." (Aug 22, 2019) en.wikipedia.org/wiki/Isovist.

[3] Wikipedia. "Visibility Polygon." (Aug 22, 2019) en.wikipedia.org/wiki/Visibility_polygon.

[4] Wikipedia. "Visibility Graph." (Aug 22, 2019) en.wikipedia.org/wiki/Visibility_graph.

[5] Wikipedia. "Art Gallery Problem." (Aug 22, 2019) en.wikipedia.org/wiki/Art_gallery_problem.

External Links

Visible Points in a Polygon

Art Gallery Theorem (Wolfram MathWorld)

Illumination Problem (Wolfram MathWorld)

Billiards (Wolfram MathWorld)

Permanent Citation

Shreyas Poyrekar, Arifa Sultana, Aaron T. Becker

"Art Gallery Problem"
http://demonstrations.wolfram.com/ArtGalleryProblem/
Wolfram Demonstrations Project
Published: September 13, 2019