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).
Monday, April 30, 2012
Saturday, April 28, 2012
Exercises of Chapter 1 (Part 3/6), Computational Geometry
Exercise 1.23. Is it possible to partition a cube into six congruent tetrahedra? Defend your answer.
Answer. Yes. The tetrahedralisation can be accomplished by performing the following procedures
1. Create a interior diagonal between two opposite vertices of the cube (any of the two most far apart)
2. Starting from each of the ends of the diagonal above created, make a diagonal on each of the three rectangular surfaces adjacent to the vertex.
3. All the above diagonals unite to characterise such a tetrahedralisation. □
Exercise 1.24. Find the six different tetrahedralisations of the cube up to rotation and reflection.
Answer. This is way harder.
It's worth classifying the tetrahedralisation first by the general way of dividing the cube, especially the first cut. We need to make sure that these classes don't overlap and also note that the shapes cut out will be triangulated individually but care needs to be taken when scoring out repeated count up to rotation and reflection.
One big class of tetrahedralisation of cube is made by dividing the cube by the surface diagonal into two congruent cheese-like prisms. The discussion of this class is ignored, it's not too hard to go through all the cases involved in it, and there should be 4 different ones up to rotation and reflection.
Naturally the other class is with tetrahedralisations that don't present separate double prisms. This class involves a special tetrahedralisation is the only one (up to rotation and reflection) that cuts the cube into 5 pieces, which consists a big tetrahedron formed by four vertices of the cube any two of those sitting on two ends of a surface diagonal, along with the remaining pieces. The other triangulation in this class is the one that first takes away two tetrahedrons each of which is with equilateral triangle base and a top just above the base sending down edges perpendicular to each other to the base and having and has the base parallel to that of the other, and then adds an internal diagonal that connects the vertices, one from each of the two bases. □
Exercise 1.25. Classify the set of triangulations on the boundary of the cube that 'induce' the tetrahedralisations of the cube, where each such tetrahedralisation matches the triangulation on the cube surface.
Answer. As all possible triangulations were generally discussed in the above exercise, the detailed answer to this question is omitted. □
Exercise 1.25. Show that the n-dimensional cube can be triangulated into exactly n! simplices.
Proof. (far from complete) Simplice that consists of as many edges as possible of a cube with edges 1 unit in length is with an n-dimensional volume of 1 / n!. As the volume of the cube is 1, there can be as many as n! simplices. □
Answer. Yes. The tetrahedralisation can be accomplished by performing the following procedures
1. Create a interior diagonal between two opposite vertices of the cube (any of the two most far apart)
2. Starting from each of the ends of the diagonal above created, make a diagonal on each of the three rectangular surfaces adjacent to the vertex.
3. All the above diagonals unite to characterise such a tetrahedralisation. □
Exercise 1.24. Find the six different tetrahedralisations of the cube up to rotation and reflection.
Answer. This is way harder.
It's worth classifying the tetrahedralisation first by the general way of dividing the cube, especially the first cut. We need to make sure that these classes don't overlap and also note that the shapes cut out will be triangulated individually but care needs to be taken when scoring out repeated count up to rotation and reflection.
One big class of tetrahedralisation of cube is made by dividing the cube by the surface diagonal into two congruent cheese-like prisms. The discussion of this class is ignored, it's not too hard to go through all the cases involved in it, and there should be 4 different ones up to rotation and reflection.
Naturally the other class is with tetrahedralisations that don't present separate double prisms. This class involves a special tetrahedralisation is the only one (up to rotation and reflection) that cuts the cube into 5 pieces, which consists a big tetrahedron formed by four vertices of the cube any two of those sitting on two ends of a surface diagonal, along with the remaining pieces. The other triangulation in this class is the one that first takes away two tetrahedrons each of which is with equilateral triangle base and a top just above the base sending down edges perpendicular to each other to the base and having and has the base parallel to that of the other, and then adds an internal diagonal that connects the vertices, one from each of the two bases. □
Exercise 1.25. Classify the set of triangulations on the boundary of the cube that 'induce' the tetrahedralisations of the cube, where each such tetrahedralisation matches the triangulation on the cube surface.
Answer. As all possible triangulations were generally discussed in the above exercise, the detailed answer to this question is omitted. □
Exercise 1.25. Show that the n-dimensional cube can be triangulated into exactly n! simplices.
Proof. (far from complete) Simplice that consists of as many edges as possible of a cube with edges 1 unit in length is with an n-dimensional volume of 1 / n!. As the volume of the cube is 1, there can be as many as n! simplices. □
Exercises of Chapter 1 (Part 2/6), Computational Geometry
Exercise 1.16 For each polygon in Figure 1.8, find the number of distinct triangulations.
Solution. Not available. Beware, have a feeling that 8abstract algebra and combination mathematics may set in.□
Exercise 1.17 For each n > 3, find a polygon with n vertices that has a unique triangulation.
Solution. The shape quickly came into my mind as it had been haunting me when thinking about the 'ears' problem. How to find something that resembles it, an umbrella, a bat, a boomerang, or a sort of B-2? nothing in real life looks exactly the same as this shape. Precisely put, it is a polygon with two long edges sharing a same vertex at a proper angle with a series of shorter edges connecting the other two ends of the edges, where all these shorter edges are pulled towards the inside, so that except for the vertex and ends thereof, all the other vertices (joining the shorter edges) have interior angles greater than 180 degrees (i.e. concave or reflex). I conjecture that this is the only 'class' of shapes that have the characteristics specified by the question.□
Exercise 1.21 For each n>3, find a polygon with n vertices with exactly two triangulations.
Solution. It can be a shape consisting of two components, being a rectangle attached to one side of the above shape with unique triangulation, where the rectangular component has exactly two triangulations and the 'wing' has unique triangulation.□
Exercise 1.22 For any n ≥ 3, show there is no polygon with n+2 vertices with exactly Cn - 1 triangulations (where Cn is the Catalan number).
Proof. Before starting the proof of this statement, I'd like to mention that proof of the theorem that the number of triangulations of a convex polygon with n+2 vertices is the Catalan number is definitely one of the most beautiful mathematical proofs I have ever seen where I can sense the traces of topology, algebra etc. at the same time, although it's just a very preliminary touch.
As a convex polygon with n+2 vertices has Cn triangulations, a concave one has Cn as well if exterior connections are regarded as diagonals as well. (so triangulation in this sense is merely a pattern of connecting vertices, or equivalently a way of connecting vertices that can be isomorphically mapped to a corresponding triangulation for the convex counterpart). We now need to exclude pure exterior triangulations from all these connection patterns. Obviously such exterior triangulations can never be one for polygons with number of vertices greater than 4 (shouldn't be very hard to prove), the statement is evident.□
Solution. Not available. Beware, have a feeling that 8abstract algebra and combination mathematics may set in.□
Exercise 1.17 For each n > 3, find a polygon with n vertices that has a unique triangulation.
Solution. The shape quickly came into my mind as it had been haunting me when thinking about the 'ears' problem. How to find something that resembles it, an umbrella, a bat, a boomerang, or a sort of B-2? nothing in real life looks exactly the same as this shape. Precisely put, it is a polygon with two long edges sharing a same vertex at a proper angle with a series of shorter edges connecting the other two ends of the edges, where all these shorter edges are pulled towards the inside, so that except for the vertex and ends thereof, all the other vertices (joining the shorter edges) have interior angles greater than 180 degrees (i.e. concave or reflex). I conjecture that this is the only 'class' of shapes that have the characteristics specified by the question.□
Exercise 1.21 For each n>3, find a polygon with n vertices with exactly two triangulations.
Solution. It can be a shape consisting of two components, being a rectangle attached to one side of the above shape with unique triangulation, where the rectangular component has exactly two triangulations and the 'wing' has unique triangulation.□
Exercise 1.22 For any n ≥ 3, show there is no polygon with n+2 vertices with exactly Cn - 1 triangulations (where Cn is the Catalan number).
Proof. Before starting the proof of this statement, I'd like to mention that proof of the theorem that the number of triangulations of a convex polygon with n+2 vertices is the Catalan number is definitely one of the most beautiful mathematical proofs I have ever seen where I can sense the traces of topology, algebra etc. at the same time, although it's just a very preliminary touch.
As a convex polygon with n+2 vertices has Cn triangulations, a concave one has Cn as well if exterior connections are regarded as diagonals as well. (so triangulation in this sense is merely a pattern of connecting vertices, or equivalently a way of connecting vertices that can be isomorphically mapped to a corresponding triangulation for the convex counterpart). We now need to exclude pure exterior triangulations from all these connection patterns. Obviously such exterior triangulations can never be one for polygons with number of vertices greater than 4 (shouldn't be very hard to prove), the statement is evident.□
Exercises of Chapter 1 (Part 1/6), Computational Geometry
Lemma 1.3. Every polygon with more than three vertices has a diagonal
Exercise 1.5. Prove that every polygonal region with polygonal holes admits a triangulation of its interior.
Proof. This proof is going to be very sketchy. Lets start with a polygon with one hole, we can use a approach similar to what was applied to prove Lemma 1.3 to find out two diagonals that both connect two different vertices on the exterior boundary of the polygon and two different vertices on the interior boundary (the boundary of the hole) without crossing any boundaries or vertices. Thus when the polygon surrounded by the two diagonals and the exterior and interior boundaries that connect the vertices on the ends of the diagonals is taken away from the polygon, the polygon becomes one without a hole. Both the remaining polygon and the polygon being taken away can be triangulated according to the previous theorem. The combined triangulation is that for the original polygon. Then using induction, the statement can be generalised to polygons containing any number of holes.□
Exercise 1.10. Prove Corollary 1.9 using induction.
Corollary 1.9. Every Polygon with more than three vertices has at least two ears
Proof. When n=4, the statement is true in that if the quadrilateral is convex it's obvious two ears can be cut out by either of its two diagonals, and if it is concave, the only diagonal marks its two ears. We assume the statement holds for all polygons with fewer than n vertices. Choose a diagonal d joining vertices a and b, cutting P into polygons P1 and P2, having n1 and n2 vertices respectively.we may have the following cases
1. Both n1 and n2 are no less than 4, then each of them has at least one ear doesn't cover the diagonal, so the original polygon they combine to from must have at least two ears.
2. One of them is a triangle, then that triangle is an ear of the original polygon.□
Exercise 1.11. Show that the sum of the interior angles of any polygon with n vertices is π(n-2).
Proof. With the availability of theorem 1.8 which states that every triangulation of a polygon P with n vertices has n-2 triangles, it's not hard to prove. As by definition, all vertices of these triangles are vertices of the polygon, the interior angles of the polygon are composed of the interior angles of all the triangles combined. As every triangle has interior angles the sum of which is π, thus we can see the for the polygon it is π(n-2).□
Exercise 1.12. Using the previous exercise, show that the total turn angle around the boundary of a polygon is 2π. Here the turn angle at a vertex v is π minus the internal angle at v.
Proof. It is pretty easy and trifling to prove this using the previous theorem.□
Exercise 1.13. Three consecutive vertices a, b, c form a mouth of a polygon if ac is an external diagonal of the polygon, a segment wholly outside. Formate and prove about the existence of mouths.
Proof. a minimal instance is a concave quadrilateral.□
Exercise 1.14. Let a polygon P with h holes have n total vertices (including hole vertices). Find a formula for the number of triangles in any triangulation of P.
Some thoughts: This is non-trivial. A good guess is n + 2(h - 1). Now comes the brief proof, suppose a newly added hole has q vertices, causing a sub-polygon of p vertices to be re-triangulated (it can be proved that the sub-polygon can be made without having a hole), by induction, the number of triangles for the sub-polygon will change from p - 2 to p+q, the net increase in number of triangles is q+2. Then it's not hard to use induction method to flesh out the proof. □
Exercise 1.15 Let P be a polygon with vertices (xi, yi) in the plane. Prove that the area of P is
1/2 | Σ (xiyi-1 - xi-1yi) |
Proof. This is a very important conclusion. Based on the guaranteed existence of triangulation, we can prove this statement by breaking down the area of the polygon into the areas of its forming triangles. □
References
1. Satyan L. Devadoss and Joseph O'Rourke 2011, Discrete and Computational Geometry, Princeton University Press Princeton and Oxford
2. HTML Special Characters, http://brucejohnson.ca/SpecialCharacters.html
3. Writing Fractions in HTML, http://changelog.ca/log/2008/07/01/writing_fractions_in_html
Exercise 1.5. Prove that every polygonal region with polygonal holes admits a triangulation of its interior.
Proof. This proof is going to be very sketchy. Lets start with a polygon with one hole, we can use a approach similar to what was applied to prove Lemma 1.3 to find out two diagonals that both connect two different vertices on the exterior boundary of the polygon and two different vertices on the interior boundary (the boundary of the hole) without crossing any boundaries or vertices. Thus when the polygon surrounded by the two diagonals and the exterior and interior boundaries that connect the vertices on the ends of the diagonals is taken away from the polygon, the polygon becomes one without a hole. Both the remaining polygon and the polygon being taken away can be triangulated according to the previous theorem. The combined triangulation is that for the original polygon. Then using induction, the statement can be generalised to polygons containing any number of holes.□
Exercise 1.10. Prove Corollary 1.9 using induction.
Corollary 1.9. Every Polygon with more than three vertices has at least two ears
Proof. When n=4, the statement is true in that if the quadrilateral is convex it's obvious two ears can be cut out by either of its two diagonals, and if it is concave, the only diagonal marks its two ears. We assume the statement holds for all polygons with fewer than n vertices. Choose a diagonal d joining vertices a and b, cutting P into polygons P1 and P2, having n1 and n2 vertices respectively.we may have the following cases
1. Both n1 and n2 are no less than 4, then each of them has at least one ear doesn't cover the diagonal, so the original polygon they combine to from must have at least two ears.
2. One of them is a triangle, then that triangle is an ear of the original polygon.□
Exercise 1.11. Show that the sum of the interior angles of any polygon with n vertices is π(n-2).
Proof. With the availability of theorem 1.8 which states that every triangulation of a polygon P with n vertices has n-2 triangles, it's not hard to prove. As by definition, all vertices of these triangles are vertices of the polygon, the interior angles of the polygon are composed of the interior angles of all the triangles combined. As every triangle has interior angles the sum of which is π, thus we can see the for the polygon it is π(n-2).□
Exercise 1.12. Using the previous exercise, show that the total turn angle around the boundary of a polygon is 2π. Here the turn angle at a vertex v is π minus the internal angle at v.
Proof. It is pretty easy and trifling to prove this using the previous theorem.□
Exercise 1.13. Three consecutive vertices a, b, c form a mouth of a polygon if ac is an external diagonal of the polygon, a segment wholly outside. Formate and prove about the existence of mouths.
Proof. a minimal instance is a concave quadrilateral.□
Exercise 1.14. Let a polygon P with h holes have n total vertices (including hole vertices). Find a formula for the number of triangles in any triangulation of P.
Some thoughts: This is non-trivial. A good guess is n + 2(h - 1). Now comes the brief proof, suppose a newly added hole has q vertices, causing a sub-polygon of p vertices to be re-triangulated (it can be proved that the sub-polygon can be made without having a hole), by induction, the number of triangles for the sub-polygon will change from p - 2 to p+q, the net increase in number of triangles is q+2. Then it's not hard to use induction method to flesh out the proof. □
Exercise 1.15 Let P be a polygon with vertices (xi, yi) in the plane. Prove that the area of P is
1/2 | Σ (xiyi-1 - xi-1yi) |
Proof. This is a very important conclusion. Based on the guaranteed existence of triangulation, we can prove this statement by breaking down the area of the polygon into the areas of its forming triangles. □
References
1. Satyan L. Devadoss and Joseph O'Rourke 2011, Discrete and Computational Geometry, Princeton University Press Princeton and Oxford
2. HTML Special Characters, http://brucejohnson.ca/SpecialCharacters.html
3. Writing Fractions in HTML, http://changelog.ca/log/2008/07/01/writing_fractions_in_html
Friday, April 27, 2012
Things to do in the weeks to come
This is a study plan for the near future, originally posted on csdn.
Mostly they are going to be computational geometry related, when put in the order of their priorities,
1. (Priority 1) Investigation into Triangularisation methods and the technologies they depend on
2. (Priority 2) 2D/3D shape relationship determination, such as whether two polygons intersect or overlap
3. (Priority 2) Spatial Indexing and Computational Geometry
4. (Priority 3) Not sure if it should be grouped with Spatial Indexing as well, it's a topic more specific to data structures for storing spatial objects so they can be easily queried
This topic should better be investigated in conjunction with spatial indexing as they are highly correlated.
(... more items are to be added as the study goes)
Thursday, April 26, 2012
Introduction
This blog is supposed to be the main technical blogging and discussion site maintained by Lincoln Yu as a replacement for the previous equivalent site on csdn which is generally in Chinese.
Contents of this site is nothing official, or representing the opinions of anyone or even Lincoln Yu.
Writing for this blog is independent of that for any other sites of similar nature or not.
Articles and other stuff on the previous site will be transferred gradually to this site with translation wherever necessary. The order in which they are moved is subject to the convenience and discretion of the author.
Contents of this site is nothing official, or representing the opinions of anyone or even Lincoln Yu.
Writing for this blog is independent of that for any other sites of similar nature or not.
Articles and other stuff on the previous site will be transferred gradually to this site with translation wherever necessary. The order in which they are moved is subject to the convenience and discretion of the author.
Subscribe to:
Comments (Atom)