Prof. Dr. Jay Martin Anderson
Professor Emeritus of Computer Science, Franklin & Marshall College
  • home
  • Development
    • Gallery
    • Stop and Pray
    • Stations at St. Thomas
    • PricePer
    • What's It Cost?
    • my own
    • at F&M
    • for clients
  • Small Gallery
  • LVC
  • Visualization
    • Algorithm Visualization >
      • Binary Space Partition
      • Convex Hull >
        • Extreme Point algorithm
        • Extreme Edge algorithm
        • "Gift Wrap" algorithm
        • Incremental algorithm
        • Incremental algorithm in three dimensions
        • "QuickHull" algorithm
      • Delaunay triangulation >
        • Incremental algorithm
        • from the Voronoi diagram
      • Line intersection >
        • a "brute force" algorithm
        • Sweepline algorithm
      • Motion planning
      • Point-in-Polygon >
        • Plumbline algorithm
        • Trapezoidal Map
        • Winding Number
      • Polygon triangulation >
        • "Art Gallery" Problem
        • Recursive algorithm
        • Make Monotone Polygons
        • Triangulate a Monotone Polygon
      • Voronoi diagram >
        • Fortune's algorithm
        • Intersection of Half-Planes
        • Quadtree algorithm
    • Data Visualization
  • OpenGL
    • OpenGL for Apple Software Developers
  • iBooks
  • about me
    • contact
Polygon Triangulation:  the "Art Gallery" problem
Picture
The "art gallery problem" asks the question:  how many guards (or cameras) does it take to guard an art gallery; that is, how many cameras do you need to be sure you can watch every wall of the gallery?

The solution to this problem begins with the triangulation of a polygon.  We use here a recursive algorithm for triangulating the polygon, which is also shown elsewhere:  connect two vertices with a diagonal which lies totally within the polygon; this decomposes the polygon into two smaller polygons.  Recursively continue until all the smaller polygons are triangles.  

If an art gallery can be an arbitrary polygon (each side is a wall of the gallery), then we can guard the gallery if we can guard each triangle formed from a triangulation of the gallery (polygon).  A triangle can always be guarded by one camera at any of its vertices.  Therefore, we need to try to find how few vertices we need for cameras in order to guard every triangle.  

After triangulating the polygon, we convert the triangulation into its dual:  a graph for which each node represents a triangle, and each edge represents a shared side of the triangulation.  We can traverse the dual graph of the triangulated polygon, coloring the vertices of each triangle as we go.  We will only need three colors. Then we can see which color was used least often; the vertices with this color are where we should put our cameras or guards.

This work was done, wholly or in part, by Anne Fairchild Peacock, F&M '02.

Click on the Download button at the right to download a zipped file of all movies described on this page.



download
Proudly powered by Weebly