hw5-sol CSE 357COMPUTATIONAL GEOMETRY Homework Set # 5 – Solution Notes

AMS 345/CSE 355 (Fall, 2019) Joe Mitchell COMPUTATIONAL GEOMETRY Homework Set # 5 – Solution Notes PROBLEMS TO TURN IN: (1). [5 points] (a). Is there a polyhedron with exactly 8 edges? Justify! (draw one, or argue that none exists) Yes, there are polyhedra with exactly 8 edges; one example is a square-based pyramid. In fact, if you think about it you should be able to argue that any 8-edge polyhedron has this structure: 4 faces that are triangles and one face that is a quadrilateral. (b). Is there a polyhedron with exactly 7 edges? Justify! (draw one, or argue that none exists) Assume there exists a 7-edge polyhedron. We will arrive at a contradiction. Let v be the number of vertices, e = 7 the number of edges, and f the number of faces of the polyhedron. We know that each vertex of any polyhedron has degree at least 3 (this follows from the definition, since a vertex must lie at the intersection of 3 or more faces (it takes 3 planes to determine a point)). Thus, the sum of the vertex degrees, which equals 2e = 14, is at least 3v: 14 ≥ 3v (which implies that the integer v must be at most 4). But the inequality e ≤ 3v − 6 (which holds for planar graphs) implies that 7 ≤ 3v − 6, so 13 ≤ 3v, which contradicts the fact that 14 ≥ 3v. Thus, a polyhedron with e = 7 cannot exist. (c). Compute the Euler characteristic and genus of the following polyhedron: Take a 3-by-3-by-3 block of unit cubes, that together form a cube of volume 3 3 = 27. (Think of a Rubik’s cube...) Index the cubes (1,1,1), (1,1,2),..., (3,3,3), so that (2,2,2) denotes the middle cube. Now, remove the 4 unit cubes that include the central unit cube (2,2,2), and the following three unit cubes that are face-adjacent to it: (3,2,2), (2,3,2), (2,2,3). The remaining polyhedron, P, is a union of 23 unit cubes. (Try to draw a picture!) Find the Euler characteristic and the genus of this polyhedron. There are 3 large (3-by-3) square faces of the block. We partition each of the 3 sides of the block that have the square “hole” into 4 convex (trapezoid) faces, by joining each of the 4 corners of the square “hole” to the corresponding corners of the larger square side of the cube. For the “removed” part, consisting of 4 unit cubes, we consider all faces to be unit squares; i.e., the 3 “L-shaped” faces are each partitioned into 3 unit squares. (NOTE: Many other partitions of the surface into convex faces work fine too; all should give the same Euler characteristic and genus, of course.) We count vertices: there are the 8 vertices of the big cube block, 4 vertices on each of 3 sides that have the square “hole” (for a total of 12 of these vertices), and another 8 vertices at the corners of the small cube in the middle, where the 3 hol