Exercise 1.28. Suppose that guards themselves block visibility so that a line of sight from one guard cannot pass through the position of another. Are there polygons for which the minimum of our more powerful guards needed is strictly less than the minimum needed for these weaker guards?
Answer. No. If this were true, then if we let the weaker guards take exactly the placement of stronger ones, the visibility of the weaker ones wouldn't cover the room. However actually it has exactly the same coverage (the linear regions blocked by one guard would actually be compensated by the sight of the blocking guard himself) □
Exercise 1.29. Prove that any quadrilateral needs only one guard to cover it. Then prove that any pentagon needs only one to cover it.
Proof. Any point on the diagonal of a quadrilateral is where the guard could stand to cover it. For pentagon there are two concave cases for each of them it is not hard to find the region of standing points. □
Exercise 1.30. Modify Lemma 1.18 to show that one guard placed anywhere in a convex can cover it.
Proof. If a line of sight gets blocked halfway by a wall, according to Jordan curve theorem, the line intersects the boundary of the shape multiple times (an odd number more than one of times) so that it repetitively leaves and enters the shape and eventually leaves, it's evident that the polygon is not a convex one (without holes). □
Exercise 1.31. Construct a polygon P and a placement of guards such that the guards see every point of ∂P but P is not covered.
Answer. A gallery in the shape of two-pronged comb with guards standing in the prongs so that they can see the corners and the pointed ends while part of the corridor might be invisible to them.
Exercise 1.34. Construct a polygon with n = 3k vertices such that placing a guard at every third vertex fails to protect the gallery.
Answer. Two-pronged comb with guards at the pointed ends of the prongs.
Exercise 1.35. Why is it not possible to easily extend Fisk's proof (of the statement that Floor(n/3) guards suffice to cover a polygon with n vertices) to the case of polygons with holes?
Answer. polygons with holes may essentially raise the number of required colours to four (at a level that amounts to what is required to colour the nodes of an arbitrary graph)
Exercise 1.36 Using exercise 1.14, derive an upper bound on the number of guards needed to cover a polygon with h holes and n total vertices. (Obtaining a tight upper bound is extremely difficult, and only recently settled.)
Answer. As is indicated by the exercise itself that the exact answer would be extremely difficult, we let ourselves loose on the question. For each hole we can find a channel diagonal that connects a vertex of the hole boundary and a vertex on the exterior or a vertex on another hole that has already been in a recursive way not connected with the exterior through the channels. Split the channels a little bit so two new vertices are introduced for each channel. Once this manipulation is done, the polygon with holes has been turned into a concave polygon with (n + 2h) vertices and without holes. According to the theorem Fisk proved, Floor((n+2h) / 3) is enough, though it obviously might not be the tight upper bound)
Exercise 1.39. Prove the Fortress theorem which declares that to cover the exterior of polygons with n vertices, Ceiling(n/2) guards are needed for some polygons, and sufficient for all of them.
Proof. If we place the guards at (or as close as possible to) every second vertex of the polygon, it is easy to see the verity of the statement. It looks like this number is only mandated for polygons with small number of vertices, such as 4 and 6.
Exercise 1.40. For any n > 3, construct a polygon P with n vertices such that Ceiling(n/3), placed anywhere on the plane, are sometimes necessary to cover the exterior of P.
Answer. Comb with blunt teeth (with 2 vertices) joining at a single points with one another and a cover to prevent a guard at a distance from overseeing the comb.
Exercise 1.41. Let P be a polyhedron with a tetrahedralisation where all edges and diagonals of the tetrahedralisation are on the boundary of P. Make a conjecture about the number of guards needed to cover P.
Answer. To me, guards placed anywhere in the tetrahedra one for each are enough to cover P. So the number sufficient for coverage can be the number of tetrahedra in a tetrahedralisation, and the actual number can be less.
Exercise 1.42 Show that even though the Schoenhardt polyhedron (Figure 1.7) is not tetrahedralisable, it is still covered by guards at every vertex.
Answer. Omitted.
Exercise 1.43 Prove the above claim, which implies that guards at every vertex of the Seidel polyhedron do not cover the entire interior. Notice that this implies that Seidel polyhedron is not tetrahedralisable.
Answer, from any point in the majority of the space inside the polyhedron surrounded by the pipes above and below, left and right, fore and aft, so long as the epsilon is small enough, any ray would hit a pipe before it gets out of the shape.
Exercise 1.44 Let n be the number of vertices of the Seidel polyhedron. What order of magnitude, as a function of n, is the number of guards needed to cover the entire interior of the polyhedron?
Answer. one guard for each of the above cells is required to illuminate the interior of the whole structure, so the order of magnitude would be Omega(n3/2).
No comments:
Post a Comment