Exercise 2.16. Prove that the point forming the largest angle to the previous edge must be a hull point.
Proof. If it is not, then there's another point with which an edge on the hull can be formed and that edge forms a smaller angle than the angle the point forms, which means the point is on the different side of the the straight line the edge is on than the polygon, therefore the point is outside, contradicting the assumption. □
Exercise 2.17. Show that this algorithm indeed produces the convex hull, closing up the polygon at the starting point.
Proof. The proof can go with two parts, the first part proving that the initial point selected is a hull point and the second being that every subsequent point chosen by the algorithm is actually the hull point adjacent to the previous one. Detail omitted. □
Exercise 2.18. We phrased the gift-wrapping algorithm in terms of angle comparison, which are notoriously slow and numerically unstable when implemented naively. Show that the angle comparison can be replaced by LEFT-OF tests, where LEFT-OF(a, b, c) is true exactly when c is left of the directed line through a and b.
Solution. Suppose the point to which the point to be attached to form the new edge is v, comparing the angles two points a and b form with the edge can be converted to determining LEFT-OF(v, a, b), specifically when the function returns true it means the angle formed by b is greater than that by a. □
Exercise 2.19. Describe a point set with n points that serves as the worst case for the gift-wrapping algorithm.
Example. A point set that itself constitutes a convex polygon. □
Exercise 2.20. Describe a point set with n points that constitutes the best-case for the gift-wrapping algorithm. What is its time complexity in this case?
Example. Three points in addition to points all inside the triangle formed by them. □
Exercise 2.21. Alter the Graham scan algorithm so that it still works for points in degenerate position.
Solution. Degenerate position for Graham scan is the situation where there are more than one point collinear with the initial point. In this case arranging them by their distance from the initial point in either ascending or descending order will resolve the degeneracy without problem. □
Exercise 2.22. Describe a point set with n points that is the worst-case for Graham scan algorithm.
Example. A boomerang shape with a head vertex at the bottom chosen as the initial point and concave (reflex) points opposite the head between two pointed vertices at the ends of the wings. □
Exercise 2.23. Given a point set S, design an algorithm that finds some polygon (any polygon) whose vertices are precisely S.
Example. A Graham scan without removing points is such an algorithm as required. □
Exercise 2.24. Design a Graham-like algorithm that first sorts the points by their x-coordinate, and then computes the 'upper' and 'lower' hulls respectively. The upper hull is found by repeatedly removing local minima, and the lower hull similarly. Detail the steps needed to realise this high-level description.
Solution. The detailed implementation / pseudo code will be present here shortly. □
Exercise 2.25. Design an algorithm to find the convex hull of a polygon in O(n) time.
Solution. Find the initial point and start going along the boundary of the polygon in specific direction (e.g. counterclockwise) by using techniques similar to what is used in Graham scan algorithm. As it walks through the points on the boundary it removes those concave points by using techniques similar to what is used to eliminate concave points by Graham scan algorithm. It can be proved that it finishes in O(n) time. □
Thursday, May 17, 2012
Monday, May 14, 2012
Exercises of Chapter 2 (Part 3/7), Computational Geometry
Exercise 2.11. Find a way to order points in the plane without moving them into general position.
Solution. For all points lying on the same vertical line, assign indices to them based on their y-coordinates so they are kept apart and can get picked up in order. □
Exercise 2.12. Alter the incremental algorithm so that it still works for point sets which may have two or more points with the same x-coordinate, without rotating the set into general position.
Solution. The algorithm is modified in such a way that the above method is used whenever points it applies to are encountered. □
Exercise 2.13. Adjust the incremental algorithm so that it still works for point sets that may include three or more collinear points.
Solution. Depending on whether points on edges can be preserved, we treat the points on detected on the tangent accordingly. The key is the edges of the current convex comprise edges visible, edges invisible and edges aligned with one of the tangents. □
Exercise 2.14. Given three points (a, b, c), detail a computation that will decide if they form a clockwise or a counterclocksise triangle.
Solution. One way (which may not be most efficient) is to check the cross product (outer product) of vector ab and ac which determines whether swiping from ab to ac goes clockwise or counterclockwise. □
Exercise 2.15. In the incremental algorithm, find a method to search for the tangent line that leads, overall, to a time complexity of O(n) rather than O(n2). Notice that this improves the speed of the algorithm to O(n log n).
Solution. The improved algorithm would keep track of the edge with the minimum inclining slope on the upper boundary and the edge with the minimum declining slope (here minimum means with minimum absolute value) on the lower boundary. It then should check the lines that connect the right ends of these edges and the point being added and decide whether and from where tangent points would be searched for and the hull thus gets updated. This is believed to help improve the speed with neither comprehensive coverage on the special cases involved in this algorithm nor detailed proof of its being able to attain O(n) being given here for the moment (elaborate algorithm will be given shortly for this exercise as well as for demonstrating the exercise before). □
Solution. For all points lying on the same vertical line, assign indices to them based on their y-coordinates so they are kept apart and can get picked up in order. □
Exercise 2.12. Alter the incremental algorithm so that it still works for point sets which may have two or more points with the same x-coordinate, without rotating the set into general position.
Solution. The algorithm is modified in such a way that the above method is used whenever points it applies to are encountered. □
Exercise 2.13. Adjust the incremental algorithm so that it still works for point sets that may include three or more collinear points.
Solution. Depending on whether points on edges can be preserved, we treat the points on detected on the tangent accordingly. The key is the edges of the current convex comprise edges visible, edges invisible and edges aligned with one of the tangents. □
Exercise 2.14. Given three points (a, b, c), detail a computation that will decide if they form a clockwise or a counterclocksise triangle.
Solution. One way (which may not be most efficient) is to check the cross product (outer product) of vector ab and ac which determines whether swiping from ab to ac goes clockwise or counterclockwise. □
Exercise 2.15. In the incremental algorithm, find a method to search for the tangent line that leads, overall, to a time complexity of O(n) rather than O(n2). Notice that this improves the speed of the algorithm to O(n log n).
Solution. The improved algorithm would keep track of the edge with the minimum inclining slope on the upper boundary and the edge with the minimum declining slope (here minimum means with minimum absolute value) on the lower boundary. It then should check the lines that connect the right ends of these edges and the point being added and decide whether and from where tangent points would be searched for and the hull thus gets updated. This is believed to help improve the speed with neither comprehensive coverage on the special cases involved in this algorithm nor detailed proof of its being able to attain O(n) being given here for the moment (elaborate algorithm will be given shortly for this exercise as well as for demonstrating the exercise before). □
Exercises of Chapter 2 (Part 2/7), Computational Geometry
Exercise 2.8. Argue that the incremental algorithm terminates.
Proof. There are infinite number of vertices and all these vertices are arranged and get picked up one at time by order, so the algorithm always terminates. □
Exercise 2.9. Let the diameter of a point set S be the largest distance between any two points of S. Prove that the diameter of S is achieved by two hull vertices.
Proof. If one of the ends of the line segment that characterises the diameter is a point inside conv(S), the line can be extended to a point on an edge, and dragging the point to one of the two adjacent vertices will definitely enlarge the diameter. □
Exercise 2.10. Prove that if S is the set of n points sampled from a uniform distribution in a unit space, then the expected number of points on the hull of S is of order O(log n).
Proof. This would be a very sketchy and flawed proof. As the particular chapter this exercise is for is considered, it's a good guess to think that it can be proved by going through the process of the algorithm. We can roughly track the possibility of introducing a new convex point for each point we pick from the uniform distributed set and add to the convex hull in the same order as specified by the algorithm. When the hull is growing in the direction parallel to Y coordinate, the possibility is about 1/k where k is the number of points that are already in the convex hull. After the four monotonously growing hull sections being merged, the total expected number will approximately be,
where α and β are generally constant coefficients that will not affect the final result in terms of order, and ε is also a negligible quantity compared to the terms in the front which as a harmonic series amounts to log n. (A program that simulates the process is expected to be present here shortly) □
Proof. There are infinite number of vertices and all these vertices are arranged and get picked up one at time by order, so the algorithm always terminates. □
Exercise 2.9. Let the diameter of a point set S be the largest distance between any two points of S. Prove that the diameter of S is achieved by two hull vertices.
Proof. If one of the ends of the line segment that characterises the diameter is a point inside conv(S), the line can be extended to a point on an edge, and dragging the point to one of the two adjacent vertices will definitely enlarge the diameter. □
Exercise 2.10. Prove that if S is the set of n points sampled from a uniform distribution in a unit space, then the expected number of points on the hull of S is of order O(log n).
Proof. This would be a very sketchy and flawed proof. As the particular chapter this exercise is for is considered, it's a good guess to think that it can be proved by going through the process of the algorithm. We can roughly track the possibility of introducing a new convex point for each point we pick from the uniform distributed set and add to the convex hull in the same order as specified by the algorithm. When the hull is growing in the direction parallel to Y coordinate, the possibility is about 1/k where k is the number of points that are already in the convex hull. After the four monotonously growing hull sections being merged, the total expected number will approximately be,
βn
α Σ 1 + ε
k=1 k
where α and β are generally constant coefficients that will not affect the final result in terms of order, and ε is also a negligible quantity compared to the terms in the front which as a harmonic series amounts to log n. (A program that simulates the process is expected to be present here shortly) □
Saturday, May 12, 2012
Exercises of Chapter 2 (Part 1/7), Computational Geometry
Exercise 2.1. Show that the use of the word 'convex' in convex hull is justified; that is, show that conv(S) is indeed a convex region.
Proof. Just proving that the intersection of any two convex hull is a convex hull is enough, which is not hard at all. However the fact that the characteristics are preserved when the intersection has been applied for infinite number of times is in a strict mathematical sense non-trivial though straightforward. □
Exercise 2.3. Let S be the four points {(0,0), (0,1), (1,0), (1,1)} in the plane. Show using Theorem 2.2 that conv(S) is the square with vertices at S.
Proof. The square can be represented by {(x,y) | 0 ≤x ≤ 1 and 0 ≤ y ≤ 1]}, so we need to prove that it is equal to conv(S), say they contain each other. The proof is not difficult and omitted. □
Exercise 2.4. For a point set S in the plane with at least four points, show that S can be partitioned into two sets A and B so that conv(A) intersects conv(B).
Proof. There are a few cases,
- If three points are collinear, then the set can be divided into a line segment between the two points at the sides of the three collinear points and a line segment between the point in the middle and the remaining point and these two line segments intersect.
- Otherwise no three points are collinear, so a triangle can be formed by any three of them, the the remaining point can either be
-- inside the triangle, in which case the first set is the triangle and the second is the remaining point
-- outside the triangle but within one of the interior angles of the triangle, in which case the first set is the line segment between the vertex the angle is around and the outside point and the second is the edge opposite the vertex.
-- outside the triangle and not within any of the interior angles but within an angle opposite an internal, in which case the outside point and the edge opposite the point the internal angle is around can form a triangle which contains the point. □
Exercise 2.5. Show that conv(S) is the convex polygon with the smallest perimeter that contains S.
Proof. If there is another one that has smaller perimeter, suppose it's P'. As a convex polygon, it has to contain all the edges of conv(S). As it's a convex polygon other than conv(S) and by definition it contains conv(S) (Note: which means there are points in P' but not in conv(S)), there must be at least one edge of conv(S) such that on the exterior side of conv(S) there are points in P', and the intersection between the straight line the edge is on and P' should be able to replace the contour of P' on the side of the straight line exterior to conv(S) without disabling P' to meet the requirements, and as line segment is the shortest between two points, it contradicts P' having the smallest perimeter. □
Exercise 2.6. Show that conv(S) is the convex polygon with the smallest area that contains S.
Proof. Just need to prove that the intersection of two convex polygons is smaller in area than either of them. □
Exercise 2.7. Show that the rectangle of smallest area enclosing a point set S has at least one of its sides flush with (i.e., containing) an edge of conv(S).
Proof. It can be seen that it's true for the case of four vertices, since as the enclosing rectangle rotates with itself contacting the quadrilateral just at its four vertices its size either monotonously varies or passes through a maximum but never a minimum (this needs some effort). And to prove this statement of exercise, only proving that the enclosing rectangle of convex polygon is enough. Notice that if the none of the edges of the enclosing polygon flushes with the edge of the convex polygon, it touches the polygon also at its four vertices and we can easily apply the above result here and find that the rectangle can never reach a minimum in such circumstances. □
Proof. Just proving that the intersection of any two convex hull is a convex hull is enough, which is not hard at all. However the fact that the characteristics are preserved when the intersection has been applied for infinite number of times is in a strict mathematical sense non-trivial though straightforward. □
Exercise 2.3. Let S be the four points {(0,0), (0,1), (1,0), (1,1)} in the plane. Show using Theorem 2.2 that conv(S) is the square with vertices at S.
Proof. The square can be represented by {(x,y) | 0 ≤x ≤ 1 and 0 ≤ y ≤ 1]}, so we need to prove that it is equal to conv(S), say they contain each other. The proof is not difficult and omitted. □
Exercise 2.4. For a point set S in the plane with at least four points, show that S can be partitioned into two sets A and B so that conv(A) intersects conv(B).
Proof. There are a few cases,
- If three points are collinear, then the set can be divided into a line segment between the two points at the sides of the three collinear points and a line segment between the point in the middle and the remaining point and these two line segments intersect.
- Otherwise no three points are collinear, so a triangle can be formed by any three of them, the the remaining point can either be
-- inside the triangle, in which case the first set is the triangle and the second is the remaining point
-- outside the triangle but within one of the interior angles of the triangle, in which case the first set is the line segment between the vertex the angle is around and the outside point and the second is the edge opposite the vertex.
-- outside the triangle and not within any of the interior angles but within an angle opposite an internal, in which case the outside point and the edge opposite the point the internal angle is around can form a triangle which contains the point. □
Exercise 2.5. Show that conv(S) is the convex polygon with the smallest perimeter that contains S.
Proof. If there is another one that has smaller perimeter, suppose it's P'. As a convex polygon, it has to contain all the edges of conv(S). As it's a convex polygon other than conv(S) and by definition it contains conv(S) (Note: which means there are points in P' but not in conv(S)), there must be at least one edge of conv(S) such that on the exterior side of conv(S) there are points in P', and the intersection between the straight line the edge is on and P' should be able to replace the contour of P' on the side of the straight line exterior to conv(S) without disabling P' to meet the requirements, and as line segment is the shortest between two points, it contradicts P' having the smallest perimeter. □
Exercise 2.6. Show that conv(S) is the convex polygon with the smallest area that contains S.
Proof. Just need to prove that the intersection of two convex polygons is smaller in area than either of them. □
Exercise 2.7. Show that the rectangle of smallest area enclosing a point set S has at least one of its sides flush with (i.e., containing) an edge of conv(S).
Proof. It can be seen that it's true for the case of four vertices, since as the enclosing rectangle rotates with itself contacting the quadrilateral just at its four vertices its size either monotonously varies or passes through a maximum but never a minimum (this needs some effort). And to prove this statement of exercise, only proving that the enclosing rectangle of convex polygon is enough. Notice that if the none of the edges of the enclosing polygon flushes with the edge of the convex polygon, it touches the polygon also at its four vertices and we can easily apply the above result here and find that the rectangle can never reach a minimum in such circumstances. □
Sunday, May 6, 2012
Exercises of Chapter 1 (Part 6/6), Computational Geometry
Exercise 1.59 Find the dihedral angles of the tetrahedra in Figure 1.26(c) and (d).
Solution. Omitted. □
Exercise 1.60 Find the dihedral angles of a regular dodecahedron.
Solution. Due to the regularity and symmetry of the shape, the dihedral angle can be calculated on any of the two adjacent planes. Angles at vertices are all 3π/5, so if we pick one of the vertices of the dodecahedron and focus on it, we'll find that a line segment starting from a point at a distance of r from this central vertex on the edge incidental to the vertex and perpendicular to one of the two edges sharing the central vertex with the one aforementioned measures r1 = r sin(3π/5) in length, and the distance between the above starting point and its counterpart on the edge remaining untouched of the three is
r2 = r√2-2cos(3π/5) . We can also create a perpendicular line segment from that point similarly. Switching to the triangle formed by the two perpendicular lines both r1 in length and the line segment connecting the two starting points r2 in length as its edges, we can see the angle between the two perpendicular lines is the questioned angle, for which if denoted by θ it is easy to figure out that the following relationship holds,
cosθ = -(cos2(2π/5) + cos(2π/5)) / sin2(2π/5). □
Exercise 1.65. Show that a regular tetrahedron cannot be scissors congruent with a cube.
Proof. There are only angles of rational multiples of π in a cube, to be precise, only angles of π/2 whether it be vertex based on dihedral. While regular tetrahedron has dihedral angles of irrational multiples of π. Note that all dihedral angles of a regular tetrahedron are the same also. According to Corollary 1.62, they are not scissors congruent. □
Exercise 1.66. Show that no Platonic solid is scissors congruent to any other Platonic solid.
Proof. We can choose d-function to be identity function on irrational multiples of π and any Dehn invariant that uses this d-function will show that it has different values between Platonic solids of different types (with it being zero for cube). □
Exercise 1.69. Let P be a 2×1×1 rectangular prism. Cut P into eight or fewer pieces and rearrange the pieces to form a cube.
Solution. Making use of the result by Exercise 1.52, we can first turn the prism into a 3√4 ×3√2 ×1 one, and then we cut the prism against the 3√4 long edge with a proportion of 3√2 to 3√2(3√2 - 1). The larger piece can serve as a base for the ultimate cube, while the smaller can further easily be shaped to a top with dimensions of 3√2 ×3√2×(√2-1). □
References
[1] Dodecahedron, Wikipedia, http://en.wikipedia.org/wiki/Dodecahedron
[2] Platonic Solid, Wikipedia, http://en.wikipedia.org/wiki/Platonic_solid
Solution. Omitted. □
Exercise 1.60 Find the dihedral angles of a regular dodecahedron.
Solution. Due to the regularity and symmetry of the shape, the dihedral angle can be calculated on any of the two adjacent planes. Angles at vertices are all 3π/5, so if we pick one of the vertices of the dodecahedron and focus on it, we'll find that a line segment starting from a point at a distance of r from this central vertex on the edge incidental to the vertex and perpendicular to one of the two edges sharing the central vertex with the one aforementioned measures r1 = r sin(3π/5) in length, and the distance between the above starting point and its counterpart on the edge remaining untouched of the three is
r2 = r√2-2cos(3π/5) . We can also create a perpendicular line segment from that point similarly. Switching to the triangle formed by the two perpendicular lines both r1 in length and the line segment connecting the two starting points r2 in length as its edges, we can see the angle between the two perpendicular lines is the questioned angle, for which if denoted by θ it is easy to figure out that the following relationship holds,
cosθ = -(cos2(2π/5) + cos(2π/5)) / sin2(2π/5). □
Exercise 1.65. Show that a regular tetrahedron cannot be scissors congruent with a cube.
Proof. There are only angles of rational multiples of π in a cube, to be precise, only angles of π/2 whether it be vertex based on dihedral. While regular tetrahedron has dihedral angles of irrational multiples of π. Note that all dihedral angles of a regular tetrahedron are the same also. According to Corollary 1.62, they are not scissors congruent. □
Exercise 1.66. Show that no Platonic solid is scissors congruent to any other Platonic solid.
Proof. We can choose d-function to be identity function on irrational multiples of π and any Dehn invariant that uses this d-function will show that it has different values between Platonic solids of different types (with it being zero for cube). □
Exercise 1.69. Let P be a 2×1×1 rectangular prism. Cut P into eight or fewer pieces and rearrange the pieces to form a cube.
Solution. Making use of the result by Exercise 1.52, we can first turn the prism into a 3√4 ×3√2 ×1 one, and then we cut the prism against the 3√4 long edge with a proportion of 3√2 to 3√2(3√2 - 1). The larger piece can serve as a base for the ultimate cube, while the smaller can further easily be shaped to a top with dimensions of 3√2 ×3√2×(√2-1). □
References
[1] Dodecahedron, Wikipedia, http://en.wikipedia.org/wiki/Dodecahedron
[2] Platonic Solid, Wikipedia, http://en.wikipedia.org/wiki/Platonic_solid
Saturday, May 5, 2012
Exercises of Chapter 1 (Part 5/6), Computational Geometry
Exercise 1.45. Find another dissection of the Greek cross, something quite different from that of Figure 1.19, that rearranges to form a square.
Solution. Omitted. □
Exercise 1.46. Find a dissection of two Greek crosses whose combined pieces form a square.
Solution. Omitted. □
Exercise 1.47. Show that any triangle can be dissected using at most three cuts and reassembled to form its mirror image. As usual, rotation and translation of the pieces are permitted, but not reflection.
Solution. (It still took a few minutes for me to figure this out) the solution is quite beautiful and it's simply based on the feasibility of dividing the triangle into three isosceles triangles by cutting along the three straight lines between its circumcenter and its three vertices. □
Exercise 1.48. Assume no three vertices of a polygon P are collinear. Prove that out of all possible dissections of P into triangles, a triangulation of P will always result in the fewest number of triangles.
Proof. We'll use induction as well as reduction to absurdity for the incremental step in the iteration. It's obviously true for triangle. Assume the theorem is true for all polygons with fewer than n vertices. If the theorem doesn't hold for polygon with n+1 vertices, which means the polygon can be dissected into less than n-1 triangles, then reducing the polygon to one with n vertices by contracting any one of the edges will lose at least one triangle (the proof of which also utilises the fact that the polygon doesn't have three vertices collinear), which indicates that the theorem doesn't hold for n. Then we see the statement is evident. □
Exercise 1.51. Let polygon P1 be scissors congruent to polygon P2, and let polygon P2 be scissors congruent to polygon P3. Show that polygon P1 is also scissors congruent to P3. In other words, show that scissors congruence is transitive.
Proof. As P2 can be formed by the pieces dissected from P1 , suppose the dissection is D12, movement (translation and rotation) is M12; And as P3 can be formed by the pieces dissected from P2, suppose the dissection is D23 and movement adhesion is M23 and adhesion is A23. So we can use the following formula to denote the process of these two transformations. Note that the movement transformation is a set of different transformations applied to the dissected pieces individually, we now clarify the definition of movement transformation to be with respect to the points (positions) in the rigid original shape. Similar definition can be made on the dissection operation (made respect to the lines as set of points in the original shape). With this clarification makes transformations commutable without changing their behaviour.
P2 = M12 D12 P1
P3 = M23 D23 P2
It's not hard to see that
P3 = M23 D23 M12 D12 P1 = M23 M12 D23 D12 P1
So we have M13 = M23 M12, D13 = D23 D12
Then the theorem follows.□
Exercise 1.52. Dissect a 2 × 1 rectangle into three pieces and rearrange them to form a 3√4 × 3√2 rectangle
References
[1] Math in HTML and CSS, http://www.cs.tut.fi/~jkorpela/math/
Solution. Omitted. □
Exercise 1.46. Find a dissection of two Greek crosses whose combined pieces form a square.
Solution. Omitted. □
Exercise 1.47. Show that any triangle can be dissected using at most three cuts and reassembled to form its mirror image. As usual, rotation and translation of the pieces are permitted, but not reflection.
Solution. (It still took a few minutes for me to figure this out) the solution is quite beautiful and it's simply based on the feasibility of dividing the triangle into three isosceles triangles by cutting along the three straight lines between its circumcenter and its three vertices. □
Exercise 1.48. Assume no three vertices of a polygon P are collinear. Prove that out of all possible dissections of P into triangles, a triangulation of P will always result in the fewest number of triangles.
Proof. We'll use induction as well as reduction to absurdity for the incremental step in the iteration. It's obviously true for triangle. Assume the theorem is true for all polygons with fewer than n vertices. If the theorem doesn't hold for polygon with n+1 vertices, which means the polygon can be dissected into less than n-1 triangles, then reducing the polygon to one with n vertices by contracting any one of the edges will lose at least one triangle (the proof of which also utilises the fact that the polygon doesn't have three vertices collinear), which indicates that the theorem doesn't hold for n. Then we see the statement is evident. □
Exercise 1.51. Let polygon P1 be scissors congruent to polygon P2, and let polygon P2 be scissors congruent to polygon P3. Show that polygon P1 is also scissors congruent to P3. In other words, show that scissors congruence is transitive.
Proof. As P2 can be formed by the pieces dissected from P1 , suppose the dissection is D12, movement (translation and rotation) is M12; And as P3 can be formed by the pieces dissected from P2, suppose the dissection is D23 and movement adhesion is M23 and adhesion is A23. So we can use the following formula to denote the process of these two transformations. Note that the movement transformation is a set of different transformations applied to the dissected pieces individually, we now clarify the definition of movement transformation to be with respect to the points (positions) in the rigid original shape. Similar definition can be made on the dissection operation (made respect to the lines as set of points in the original shape). With this clarification makes transformations commutable without changing their behaviour.
P2 = M12 D12 P1
P3 = M23 D23 P2
It's not hard to see that
P3 = M23 D23 M12 D12 P1 = M23 M12 D23 D12 P1
So we have M13 = M23 M12, D13 = D23 D12
Then the theorem follows.□
Exercise 1.52. Dissect a 2 × 1 rectangle into three pieces and rearrange them to form a 3√4 × 3√2 rectangle
Solution. Omitted. □
Exercise 1.55. Following the proof of the Bolyai-Gerwein theorem, what is the actual number of pieces that results from transforming the Greek cross into a square? Assume the total area of the square is 5/2 and use Figures 1.24 and 1.25 for guidance.
Solution. Tedious and trivial. Leaving it to the computer to solve is even more interesting. Solution omitted. □
Exercise 1.56. Show that a square and a circle are not scissors congruent, even permitting curved cuts.
Proof. It's not easy to put it down in detail and in strict mathematical manner, however a sketchy explanation is enough, which reveals the fact that each cut for the arc of the circle will just create one more arc of the same size for it to match, and consequently it will never form a shape without curved boundary. □
[1] Math in HTML and CSS, http://www.cs.tut.fi/~jkorpela/math/
Thursday, May 3, 2012
Topics on Binary Search
Binary Search is notorious for its being both strikingly straightforward from a theoretical point of view and comparatively hard and error-prone when it comes to implementation for a specific occasion (It costs you more time than you would have expected and you might face even more issues coding and debugging it than you have ever expected as well if you are not among those few who are quite comfortable with dealing with boundary conditions). Moreover, it's indeed one of the most frequently used algorithms in the entire computing world. Microsoft .NET framework did quite a good job to incorporate this method as part of its array class, but it is still a few steps short of providing a general method to cover all the potential data structures that it might apply to. Apart from .NET, there are heaps of situations where this method is not available. That's why I really wanted to make a note of a few versions of binary search method here for future reference.
Following is the version I wrote in answer to a call on for such implementations from a post on csdn.
The code is written in sort of the programming language ADA, which I think due to its generic nature can be easily transformed to any other languages. It has been roughly tested, however the correctness or the universal applicability is not guaranteed.
-- Find out the location of an item specified as 'e' if it exists
-- or where it should be inserted if otherwise
-- in the list specified as 'l' of comparable items of type 'element_t'
-- in ASCENDING order
-- in the range between the index of the first item specified as 'first' (inclusive)
-- and the index of the last item specified as 'last' (exclusive)
-- and return the resultant index as 'index_t' and a boolean value 'found' indicating
-- whether the item exists or not
procedure binarysearch(l : list_t; first, last : index_t; e : element_t;
index : out index_t; found : out boolean) is
lo : index_t := first; -- lowest index
hi : index_t := last + 1; -- highest index plus one
mi : index_t; -- middle index
vm : element_t; -- item at the middle index
begin
while lo < hi loop -- Note: this can be relaxed to 'lo != hi'
mi := (lo + hi) / 2;
vm := get(l, mi);
if e < vm then -- flip the operator and that below for DESCENDING order
hi := mi;
elsif vm < e then
lo := mi + 1;
else -- vm equals e, the item is found
index := mi;
found := true;
return;
end if;
end loop;
index := lo; -- item not found, the index it should be
found := false; -- inserted at is returned
end;
Although I'm quite happy with the above implementation, as mentioned the algorithm may have quite a few variants, which would be added down here later on once it comes up and the author finds it interesting and noteworthy.
Following is the version I wrote in answer to a call on for such implementations from a post on csdn.
The code is written in sort of the programming language ADA, which I think due to its generic nature can be easily transformed to any other languages. It has been roughly tested, however the correctness or the universal applicability is not guaranteed.
-- Find out the location of an item specified as 'e' if it exists
-- or where it should be inserted if otherwise
-- in the list specified as 'l' of comparable items of type 'element_t'
-- in ASCENDING order
-- in the range between the index of the first item specified as 'first' (inclusive)
-- and the index of the last item specified as 'last' (exclusive)
-- and return the resultant index as 'index_t' and a boolean value 'found' indicating
-- whether the item exists or not
procedure binarysearch(l : list_t; first, last : index_t; e : element_t;
index : out index_t; found : out boolean) is
lo : index_t := first; -- lowest index
hi : index_t := last + 1; -- highest index plus one
mi : index_t; -- middle index
vm : element_t; -- item at the middle index
begin
while lo < hi loop -- Note: this can be relaxed to 'lo != hi'
mi := (lo + hi) / 2;
vm := get(l, mi);
if e < vm then -- flip the operator and that below for DESCENDING order
hi := mi;
elsif vm < e then
lo := mi + 1;
else -- vm equals e, the item is found
index := mi;
found := true;
return;
end if;
end loop;
index := lo; -- item not found, the index it should be
found := false; -- inserted at is returned
end;
Although I'm quite happy with the above implementation, as mentioned the algorithm may have quite a few variants, which would be added down here later on once it comes up and the author finds it interesting and noteworthy.
Subscribe to:
Comments (Atom)