Problems
a. Can every plane (non-self-intersecting) polygon be triangulated
to form a graph where every vertex has valence at most s? (Or,
can you find a family of polygons Pt such that for every triangulation
of Pt there is a vertex of valence at least t?)
b. Can you find a family of plane (non-self-intersecting) polygons
Pt which have exactly t ways to triangulate the polygon?
c. Explore the possibility of some connection between the number
of guards of a polygon and number of different ways to triangulate
the polygon. (The number of guards for a polygon is the minimum
number of points in the polygon from which all of the polygon
is collectively visible from one or more of the points.)
(See Project 1.)
References
1. O'Rourke, J., Art Gallery Theorems and Algorithms, Oxford University
Press, New York, 1987.
Previous | Home | Glossary | Next