Book edition 7th

Author(s) Kenneth H. Rosen

Pages 808 pages

ISBN 9780073383095

Answers without the blur.

Just sign up for free and you're in.

Short Answer

Solve the art gallery problem by proving the art gallery theorem, which states that at most (n/3) guards are needed to guard the interior and boundary of a simple polygon with n vertices.
(Hint: Use Theorem 1 in Section 5.2 to triangulate the simple polygon into n - 2 triangles. Then show that it is possible to color the vertices of the triangulated polygon using three colors so that no two adjacent vertices have the same color. Use induction and Exercise 23 in Section 5.2. Finally, put guards at all vertices that are colored red, where red is the color used least in the coloring of the vertices. Show that placing guards at these points is all that is needed.)

proved.

\(g(n) = \frac{n}{{3j}}\)

See the step by step solution

Step by Step Solution

TABLE OF CONTENTS :

TABLE OF CONTENTS

Step-1 Given Information

The art gallery problem by proving the art gallery theorem.

The steps required to solve the given problem are,

1. Triangulate with algorithms.

2. Generate 3-coloring by DFS.

3. Take the smallest color class to place the guards.

Step-2 Definition and Formula

The art gallery problem is formulated in geometry as the minimum number of guards that need to be placed in an n-vertex simple polygon such that all points of the interior are visible. A simple polygon is a connected closed region whose boundary is defined by a finite number of line segments. Visibility is defined such that two points u and v are mutually visible if the line segment joining them lies inside the polygon

Step-3 Prove

Let \(v\) is the leftmost vertex and \(u\) and \(w\) its two neighbors.

The triangle formed by\(u\),\(v\),w contains at least one vertex.

Let \(v\) be the one closest to \(v\). Then\(w\)is a diagonal. The diagonal splits the polygon into two which by induction can be triangulated. Triangles \(I - 2\)

Any diagonal splits P into two simple polygons with k and m vertices, respectively.

By induction these two sub polygons can be triangulated. They are decomposed into \(K - 2\) and,,,-2 triangles, respectively. Vertices defining the diagonal occur in each sub polygon once. Other vertices of P can each occur in exactly one sub polygon. We have, \(K + m = n + 2\)By induction, the triangulation of P has \((K - 2) \div (m - 2) = n - 2\)

triangles.

In order to prove the second half, allow us to assume that it's attainable to paint the vertices of the triangulated plane figure mistreatment of 3 colors in such a way that no 2 adjacent vertices have an equivalent color, this could be evidenced by induction, the premise step is trivial.

Assume the inductive hypothesis that each triangulated plane figure with k vertices is 3-colored, and think about a triangulated plane figure with k vertices (since one among the triangles within the triangulation has 2 sides that were sides of the initial polygon). A triangulated plane figure with K vertices is obtained by removing those 2 sides and their common vertex Therefore, we will have 3-color or vertices. Currently place the removed edges and vertex back. The vertex is adjacent to solely 2 alternative vertices, therefore we will extend the coloring to that by distribution it the color not employed by those vertices. Coming to the final part we know that some color must be used no more than n/3 times otherwise it would result in more than, vertices If red is the color used least in our coloring then there are at most vertices colored red, and since this being an integer, there are at most colored red We put guards at all red vertices

Hence proved.

\(g(n) = \frac{n}{{3j}}\)

Find Study Materials for

Create Study Materials

Select your language

Discrete Mathematics and its Applications

Answers without the blur.

Short Answer

Step by Step Solution

Step-1 Given Information

Step-2 Definition and Formula

Step-3 Prove

Most popular questions for Math Textbooks

Want to see more solutions like these?

Recommended explanations on Math Textbooks

Select your language

Discrete Mathematics and its Applications

Answers without the blur.

Short Answer

Step by Step Solution

Step-1 Given Information

Step-2 Definition and Formula

Step-3 Prove

Most popular questions for Math Textbooks

Want to see more solutions like these?

Recommended explanations on Math Textbooks

Decision Maths

Calculus

Probability and Statistics

Statistics

Mechanics Maths

Geometry

Pure Maths