Art Gallery Problem

Requires a Wolfram Notebook System

Interact on desktop, mobile and cloud with the free Wolfram Player or other Wolfram Language products.

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.

Contributed by: Shreyas Poyrekar, Arifa Sultana and Aaron T. Becker (September 2019)
Open content licensed under CC BY-NC-SA


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.

Reference

[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.


Snapshots



Feedback (field required)
Email (field required) Name
Occupation Organization
Note: Your message & contact information may be shared with the author of any specific Demonstration for which you give feedback.
Send