4. art gallery_with-VOICE(2)(1)(1)

1.

Guarding and Triangulation
Outline
I. Properties of polygon triangulation
II. Solution to the art gallery problem
Textbook: Computational Geometry: Algorithms and Applications (3rd ed.) by M. de Berg et al., Springer-Verlag, 2008.

2. The Art Gallery Problem

camera
How many cameras are needed to guard a gallery?
Where should they be placed?

3. I. Simple Polygon Model

Model the art gallery as a region bounded by some simple
polygon (no self-crossing).
Regions with holes are not allowed.
convex polygon
one camera
an arbitrary