Chapter 10: Q42E (page 735)
Show that g(3)=1 and g(4)=1 by showing that all triangles and quadrilaterals can be guarded using one point.
Short Answer
It is Proved that g(3)=1and g(4)=1 showing that all triangles and quadrilaterals can be guarded using one point.
Step by step solution
Over 22 million students worldwide already upgrade their learning with Vaia!
Given Information
Triangles and Quadrilaterals
Related Definitions
x covers or sees a point y, if entire line segment xy lies in the simple polygon P or n its boundary.
Guarding set of a simple polygon P is every point y in P, there exists a point z in the guarding set that sees y.
G(P)= minimum value of G(P) of points required in the guarding set of P
g(n)= maximum values of G(P) over all simple polygons P with n vertices.
Proving that g(3)=1 and g(4)=1 by showing that all triangles can be guarded using one point
A simple polygon with 3 vertices is a Triangle.
No matter which point x you select in a triangle, this point x will be able to see all other points y in or on the triangle (as triangles are always convex polygon and every vertex in a convex polygon can be seen by all points on or inside the polygon).
This implies that as G(P) needs to contain any one vertex and thus g(3) is equal to 1.
g(3)=1
Proving that g(3)=1 and g(4)=1 by showing that all Convex Quadrilaterals can be guarded using one point
A simple Polygon with 4 vertices is a quadrilateral.
No matter with point x you select in a convex quadrilateral, this point x will be able to see all other points y in or on the convex quadrilateral (property convex polygons).
This implies that G(P) needs to contain at least one vertex and thus g(4) is equal to 1.
g(4)=1
Proving that g(3)=1 and g(4)=1 by showing that all Non-Convex Quadrilaterals can be guarded using one point
Since the sum of all 4 angles in a quadrilateral is 360, a quadrilateral contains at most one vertex with an angle of more than 180.
If we then select the vertex of with the angle of more than 180, then this vertex can see all other points in the quadrilateral and thus G(P) needs to contain at least one vertex which implies that g(4)=1
g(4)=1
