Exercise 3.19 For every n, construct a point set (not necessarily in general position) with n points whose flip graph is a single node, that is no flip is possible.
Solution. The boomerang(umbrella), or the crown(saw) for odd numbers. □
Exercise 3.20 For every n (greater than 3), construct a point set (not necessarily in general position) with n points whose flip graph is two nodes connected by an arc.
Solution. A properly organised boomerang shape with a spike sticking out from any of its shorter edges where the only flip can be made within the quadrilateral formed by it and the apex. □
Exercise 3.20 Figure 3.8 shows a triangulation for three different point sets. For each point set, find its flip graph.
Solution. (a) Only can flip in each of the three trapezoid; (b) quite a lot; (c) ... □
Exercise 3.23 Prove that if pn, a, and b are the only convex vertices in the star of pn, then the star of pn in T is exactly the star of pn in T*.
Proof. We prove it using Reductio ad absurdum. If they are different, there are two possible cases
- One is totally inside the other. It's easy to find that the bigger one must not be a valid star.
- The two reflex lines intersect somewhere. Then we can always pick points from the line between a and b other than the line passing through
pn , from the intersection of the two stars to form a star smaller than both of the two original so-called stars, and prove that they are actually not. □
Exercise 3.24 Prove or disprove: no point set can have a triangle as a subgraph of its flip graph, that is, three nodes connected in a cycle by three arcs.
Proof. Triangulation A flips and becomes B, if B flips on the same quadrilateral, it turns back to A and thus has no way to become a third triangulation C. Therefore B has to flip another quadrilateral, if it doesn't overlap the said one, then C cannot flip back to A since it's different than A in two quadrilaterals; if they overlap, C still cannot flip back to A since there are two different edges. □
Exercise 3.26 Find the diameters of the flip graphs of the point sets given in Figure 3.8.
Solution. (a) 3 (b) ... (c) ... □
Exercise 3.27 Find the diameter of the flip graph of the point set given in Figure 3.5.
Solution. (n-1)2 (where n is the number of vertices in each of the chains; proof and process omitted) □
Exercise 3.29 Figure 3.10 shows two triangulations from Figure 3.2 along with their overlapping diagram with 16 edge crossings. Verify Theorem 3.28 by finding a path in the flip graph between the two triangulations with no more than 16 flips.
Solution. Omitted. □
Exercise 3.30 Let S be a point set with h points on the hull and k points interior to the hull. Prove that the number of crossings of edges in T12 is at most (3k+h-3)2.
Proof. Actually this upper bound is too relaxed. Simply use the fact that the number of internal edges is 3k+h-3. □
Exercise 3.30 Show that this incremental algorithm indeed results in a partition of the convex hull into tetrahedral pieces.
Proof. May need first to clarify the difference between tetrahedralisation in this sense and that that is discussed in the previous chapter which is not feasible for some special point sets. The former is based on a set of points without any restriction on the 3D shape (polyhedron) they form, and the shape that the triangulation covers has to be the convex hull of the point set. Apart from this, the process of incremental algorithm generalised to 3D is simply collecting vertices in general position in the order determined by the lexicographical ordering to create a tetrahedralised set as it does with 2D. □
Exercise 3.33 If the point set S were not in general position, how would this affect the number of tetrahedra?
Solution. Vertices that happen to be on edges would split the tetrahedra that share the edge into two (if the edge is on the hull there would be two tetrahedra; if the edge is interior the number is indefinite (so the ultimate number may increase as opposed to the general position case); Vertices that happen to be on surfaces would split the one or two tetrahedra that contain the surface into three. □
Exercise 3.34 Based on the proof of the theorem, how can we find tetrahedralisations with fewer than 3k+2h-7 tetrahedra?
Solution. Start from a vertex with more than 3 incident hull triangles. (Since 3h < 2e, for all e > 6, can always find such a vertex according to pigeonhole principle) □
Exerciese 3.35 For arbitrary n > 4, construct an n-point set in R3 (not necessarily in general position) with a tetrahedralisation having at most n - 3 tetrahedra.
Solution. A n-point point set with all vertex other than one on the same plane.
Exercise 3.36 Let T be a point set consisting of the four vertices of a regular tetrahedron. Is it possible to add points P interior to T such taht the tetrahedralisation of the point set T U P results in only regular tetrahedra?
Answer. No. Even vertices are allowed to be added on the hull. As it were possible, the triangles on the hull would be triangulated into equilateral triangles which is possible and has to be done in such a way that all the triangles have their edges parallel to any of the three edges of the containing triangle. But based on this it would not build up a tetrahedralisation of regular triangles, since there is no way to tetrahedralise regular octahedra which remain after cutting into smaller regular tetrahedrons. □
Exercise 3.37 Constructs the flip graph of eight points in R3 whose convex hull forms a cube.
Solution. Should be interesting and not too difficult. Omitted. □
Tuesday, September 25, 2012
Tuesday, July 31, 2012
A Blind Spot in C++ Destructor
I have known for long that in the constructors of a class in C++ and literally any major modern Object Oriented programming languages, the virtual methods of the class are not to work as one might expect - in fact only the method defined in the class that contains the constructor that is being executed is to be executed from within the constructor rather than the overriding one located in the class of which the object to be created is an instance, the reason simply being that the run-time information of the derived class on which the invocation of the overriding method(s) depends at this stage hasn't been created as the order of constructing is always from the base class to the derived. Note this is one of the questions I was given in a interview with google at Shanghai and I didn't get quite right. I have fully understood the significance of it since then as it's so fundamental and it will both enhance your code at a potentially architectural level and save you time debugging.
However, recently I found it was not the end. Despite the simplicity of that, it seems I didn't learn a proper lesson from it. This morning I encountered a similar issue, not with constructor but with destructor (which in C# dialect may also be known as 'finaliser'). I finally decided to extend a dialog class to deal with some importing and exporting stuff so that objects of a layer and of particular types recently implemented could be exchanged with files of GIS format as those of all the other layers were, and in the extended class I defined a exporter instance for polylines in addition to the existing one in the base class for polygons. I didn't forget to write the overriding methods for closing the files and doing other cleanup, nor did I forget to call the corresponding base methods from the overriding methods as appropriate or mark all the relevant methods 'virtual'. However the separate file for polylines never got exported correctly. As it had worked properly when done by simply adding logic to the base, so I was pretty sure the methods are logically correct. After quite a bit of debugging, comparisons and analysis, I found the problem was indeed to do with finalising which I had been suspecting most. Since the calling of finalising method was only made in the destructor of the base class, the overriding finalising method in the derived class never got called. The principle behind is the almost same as that behind the constructor, the only difference is the order is reversed - the destructor in the base class as is called last never has any knowledge of the derived class and is unable to call the overriding method.
The conclusion, to be simple, is that as you should avoid whatever attention you should pay with regards to virtual method calls from a constructor should equally be paid to those from a destructor.
An example of how this plays a part in a real programming paradigm,
The following is a typical and standard way of defining a class that implements IDisposable interface
class DisposableObject : IDisposable
{
protected bool disposed; // or any member that can indicate if the
// object has been finalised in any way
// however unlike what's suggested by most
// of the resources it should be made accessible
// from a derived class to make this inherited
// disposal implementation to work (unless a
// separate one is set up in the derived class)
~DisposableObject()
{
Dispose(false); // called from destructor
}
// As it's an implementation of IDisposable method, it has to be public
// And as it's normally called on the interface instance, it doesn't have
// to be declared virtual
public void Dispose()
{
Dispose(true); // called from diposing method
GC.SuppressFinalize(this);
}
// Dispose of managed resources, this is a safe and logic method
// that has already been widely practised,
// http://msdn.microsoft.com/en-us/library/system.idisposable.dispose.aspx
protected virtual void Dispose(bool disposing)
{
if (!disposed)
{
if (disposing)
{
// Dispose of managed resources
// ...
}
// cleanup unmanaged resources
// ...
disposed = true;
}
}
}
However the derived disposable class is rarely looked at. According to the above analysis of how destructors work, it should be like,
class DerivedDisposableObject : DisposableObject
{
~DisposableObject()
{
Dispose(false); // must not rely on the base class to dispose if an
// overriding method is defined; the base Dispose method
// will be called from the base destructor but its
// internal will not be unnecessarily executed as the
// flag of 'disposed' has already been flipped here
}
// void (IDispose.)Dispose() is not necessary (unless it's different to
// the base) since it's not at the finalising stage and the overriding method
// would be properly invoked from base class
protected virtual void Dispose(bool disposing)
{
if (!disposed)
{
if (disposing)
{
// Dispose of managed resources
// ...
}
// cleanup unmanaged resources
// ...
// DO NOT set 'disposed' to true as the base method needs it
base.Dispose(disposing);
}
}
}
However, recently I found it was not the end. Despite the simplicity of that, it seems I didn't learn a proper lesson from it. This morning I encountered a similar issue, not with constructor but with destructor (which in C# dialect may also be known as 'finaliser'). I finally decided to extend a dialog class to deal with some importing and exporting stuff so that objects of a layer and of particular types recently implemented could be exchanged with files of GIS format as those of all the other layers were, and in the extended class I defined a exporter instance for polylines in addition to the existing one in the base class for polygons. I didn't forget to write the overriding methods for closing the files and doing other cleanup, nor did I forget to call the corresponding base methods from the overriding methods as appropriate or mark all the relevant methods 'virtual'. However the separate file for polylines never got exported correctly. As it had worked properly when done by simply adding logic to the base, so I was pretty sure the methods are logically correct. After quite a bit of debugging, comparisons and analysis, I found the problem was indeed to do with finalising which I had been suspecting most. Since the calling of finalising method was only made in the destructor of the base class, the overriding finalising method in the derived class never got called. The principle behind is the almost same as that behind the constructor, the only difference is the order is reversed - the destructor in the base class as is called last never has any knowledge of the derived class and is unable to call the overriding method.
The conclusion, to be simple, is that as you should avoid whatever attention you should pay with regards to virtual method calls from a constructor should equally be paid to those from a destructor.
An example of how this plays a part in a real programming paradigm,
The following is a typical and standard way of defining a class that implements IDisposable interface
class DisposableObject : IDisposable
{
protected bool disposed; // or any member that can indicate if the
// object has been finalised in any way
// however unlike what's suggested by most
// of the resources it should be made accessible
// from a derived class to make this inherited
// disposal implementation to work (unless a
// separate one is set up in the derived class)
~DisposableObject()
{
Dispose(false); // called from destructor
}
// As it's an implementation of IDisposable method, it has to be public
// And as it's normally called on the interface instance, it doesn't have
// to be declared virtual
public void Dispose()
{
Dispose(true); // called from diposing method
GC.SuppressFinalize(this);
}
// Dispose of managed resources, this is a safe and logic method
// that has already been widely practised,
// http://msdn.microsoft.com/en-us/library/system.idisposable.dispose.aspx
protected virtual void Dispose(bool disposing)
{
if (!disposed)
{
if (disposing)
{
// Dispose of managed resources
// ...
}
// cleanup unmanaged resources
// ...
disposed = true;
}
}
}
However the derived disposable class is rarely looked at. According to the above analysis of how destructors work, it should be like,
class DerivedDisposableObject : DisposableObject
{
~DisposableObject()
{
Dispose(false); // must not rely on the base class to dispose if an
// overriding method is defined; the base Dispose method
// will be called from the base destructor but its
// internal will not be unnecessarily executed as the
// flag of 'disposed' has already been flipped here
}
// void (IDispose.)Dispose() is not necessary (unless it's different to
// the base) since it's not at the finalising stage and the overriding method
// would be properly invoked from base class
protected virtual void Dispose(bool disposing)
{
if (!disposed)
{
if (disposing)
{
// Dispose of managed resources
// ...
}
// cleanup unmanaged resources
// ...
// DO NOT set 'disposed' to true as the base method needs it
base.Dispose(disposing);
}
}
}
Wednesday, July 4, 2012
Exercises of Chapter 3 (Part 1/5), Computational Geometry
Exercise 3.2 Show that the edges of the convex hull of a point set S will always be in every triangulation of S.
Proof. Because they are not crossing any of the edges other than themselves that have two points of S as its end points. □
Exercise 3.3 The definition of a triangulation of a point set does not even mention "triangles". Show that all the regions of subdivision inside the convex hull must indeed be triangles
Proof. The definition is repeated here again
A triangulation of a planar point set S is a subdivision of the plane determined by a maximal set of non-crossing edges whose vertex set is S.
As they are non-crossing each regions of subdivision must be a polygon. However if it's a polygon with more than 3 vertices, it can be further divided thus the set has yet to reach maximum.□
Exercise 3.4 Extend the triangle-splitting algorithm to work for points that may include three or more collinear points (but not all collinear)
Solution. Find the convex hull first leaving all the points on the edges of the hull between vertices out. Triangulate the hull ignoring again all the points on the edges. Performing the proceedings of the original algorithm for all points strictly interior to existing triangles with again points on edges ignored. Finally triangulate all the triangles just triangulated with points on edges.□
Exercise 3.5 Analyse the time complexity of the triangle-splitting algorithm.
Analysis. Only the original algorithm for non-collinear point set is considered. Hull finding takes O(n log n). Suppose there are m points on the hull, then there are m-2 triangles created by the initial triangulation, and m-n points inside. Each point to be added needs to be checked against all existing triangles and adds two triangles to the triangulation once added. The check determines if the point is inside the particular triangle, which take constant time. So this phase has (m+n-5)(n-m)/2 steps which is basically O(n2). Therefore the overall complexity is O(n2). □
Exercise 3.7 Prove or disprove: The triangle-splitting algorithm produces all possible triangulations of a point set.
Disprove (It's not true). As the triangulation produced by this algorithm has the restriction that it must contain diagonals of the hull, a counter-example can easily made by a triangulation of point set which doesn't contain any diagonals of the hull. □
Exercise 3.8 Analyse the complexity of the incremental algorithm.
Analysis. Sorting takes O(n log n); Visibility testing for about n nodes requires O(n2) time at minimum (by keeping track of the hull and performing the same process as for convex hull finding). So the overall complexity is O(n2). □
Exercise 3.9 Prove that the incremental algorithm produces a triangulation of a point set in general position.
Prove. Just discuss a special case where three points are collinear and the point behind is not considered as it's not visible to the current point, which is fine as it's the right way to do the triangulation. □
Exercise 3.10 Prove or disprove: The incremental algorithm produces all possible triangulations of a point set in general position.
Disprove (It's not true). Imagine a big triangle with quite a few points near all of its three edges exterior to the triangle, when properly set this point set can never be triangulated in such a way that the edges of big triangle remain. □
Exercise 3.11 Alter the Graham scan convex hull algorithm (Section 2.4) to compute triangulations.
Solution. Each time a new vertex is being processed, it should be combined with the latest edge scanned through to form a new triangle. For each reflex point (with right turn) encountered in the scanning process, simply add the triangle formed by the point and the edge introduced to eliminate the right turn. □
Exercise 3.14 Show that every triangulation has some vertex of degree at most five.
Proof. Use theorem 3.13 which declares that any triangulation of point set with n = k + h points where k is the the number of interior vertices and h that of those on the hull has 3k + 2h - 3 edges. Those edges are shared by those vertices. So the summed degree of the vertices is twice the edge number, which is 6k + 4h - 3, distributed to n vertices. According to pigeon hole principle at least one vertex has degree no more than ⌊( 6k + 4h - 3 ) / (k + h)⌋ = ⌊6 - ( 2h + 3 ) / (k + h)⌋ ≤ 5. □
Exercise 3.15 Construct a point set S with n+2 points such that the number of triangulations of S is greater than Catalan number Cn.
Example. See the example in Exercise 3.18 when n gets to 6. □
Exercise 3.17 Compare this value (30n, which is the upper bound of number of triangulations of an arbitrary point set) with Catalan number derived in Theorem 1.19.
Analysis. Number of triangulations of convex hull with n vertices is Cn-2, this number is generally smaller and growing (at a rate lower than 4) much slower than 30n. □
Exercise 3.18 Consider the point set S given in Figure 3.5. It is made of two "double chains" of points, where every pair of points from different chains is visible to each other. Show that the edges drawn in the figure appear in every triangulation of S. Moreover, if there are n points in each chain, find the number of triangulations of S.
Proof. If two points are not connected in a triangulation there must be an edge in the triangulation going across the edge that connects the two points. As every pair of points from different chains is visible to each other, it can be proved that there is no such edge for all the edges drawn in the figure.
Solution to the question. If we use T(m,n) to denote the number of triangulations between the chains of a point set which takes m points from the upper chain and n from the lower chain (it can be proved that this measurement is always applicable to this point set and any of its subsets). It is easy to see the following relationships
T(m,n) = T(n,m)
T(m,n) = T(m-1,n) + T(m,n-1)
T(m,1) = 1
The above relationships lead to T(m,n) = C(m+n-2, m-1) and T(n,n) = C(2n-2, n-1) where C is the combination function.
The polygon enclosed by either of the chain and the horizontal line attached to the chain is a convex polygon so it independently has Catalan(n-2) triangulations, therefore the total number of triangulations is Catalan(n-2)2 C(2n-2,n-1). □
Proof. Because they are not crossing any of the edges other than themselves that have two points of S as its end points. □
Exercise 3.3 The definition of a triangulation of a point set does not even mention "triangles". Show that all the regions of subdivision inside the convex hull must indeed be triangles
Proof. The definition is repeated here again
A triangulation of a planar point set S is a subdivision of the plane determined by a maximal set of non-crossing edges whose vertex set is S.
As they are non-crossing each regions of subdivision must be a polygon. However if it's a polygon with more than 3 vertices, it can be further divided thus the set has yet to reach maximum.□
Exercise 3.4 Extend the triangle-splitting algorithm to work for points that may include three or more collinear points (but not all collinear)
Solution. Find the convex hull first leaving all the points on the edges of the hull between vertices out. Triangulate the hull ignoring again all the points on the edges. Performing the proceedings of the original algorithm for all points strictly interior to existing triangles with again points on edges ignored. Finally triangulate all the triangles just triangulated with points on edges.□
Exercise 3.5 Analyse the time complexity of the triangle-splitting algorithm.
Analysis. Only the original algorithm for non-collinear point set is considered. Hull finding takes O(n log n). Suppose there are m points on the hull, then there are m-2 triangles created by the initial triangulation, and m-n points inside. Each point to be added needs to be checked against all existing triangles and adds two triangles to the triangulation once added. The check determines if the point is inside the particular triangle, which take constant time. So this phase has (m+n-5)(n-m)/2 steps which is basically O(n2). Therefore the overall complexity is O(n2). □
Exercise 3.7 Prove or disprove: The triangle-splitting algorithm produces all possible triangulations of a point set.
Disprove (It's not true). As the triangulation produced by this algorithm has the restriction that it must contain diagonals of the hull, a counter-example can easily made by a triangulation of point set which doesn't contain any diagonals of the hull. □
Exercise 3.8 Analyse the complexity of the incremental algorithm.
Analysis. Sorting takes O(n log n); Visibility testing for about n nodes requires O(n2) time at minimum (by keeping track of the hull and performing the same process as for convex hull finding). So the overall complexity is O(n2). □
Exercise 3.9 Prove that the incremental algorithm produces a triangulation of a point set in general position.
Prove. Just discuss a special case where three points are collinear and the point behind is not considered as it's not visible to the current point, which is fine as it's the right way to do the triangulation. □
Exercise 3.10 Prove or disprove: The incremental algorithm produces all possible triangulations of a point set in general position.
Disprove (It's not true). Imagine a big triangle with quite a few points near all of its three edges exterior to the triangle, when properly set this point set can never be triangulated in such a way that the edges of big triangle remain. □
Exercise 3.11 Alter the Graham scan convex hull algorithm (Section 2.4) to compute triangulations.
Solution. Each time a new vertex is being processed, it should be combined with the latest edge scanned through to form a new triangle. For each reflex point (with right turn) encountered in the scanning process, simply add the triangle formed by the point and the edge introduced to eliminate the right turn. □
Exercise 3.14 Show that every triangulation has some vertex of degree at most five.
Proof. Use theorem 3.13 which declares that any triangulation of point set with n = k + h points where k is the the number of interior vertices and h that of those on the hull has 3k + 2h - 3 edges. Those edges are shared by those vertices. So the summed degree of the vertices is twice the edge number, which is 6k + 4h - 3, distributed to n vertices. According to pigeon hole principle at least one vertex has degree no more than ⌊( 6k + 4h - 3 ) / (k + h)⌋ = ⌊6 - ( 2h + 3 ) / (k + h)⌋ ≤ 5. □
Exercise 3.15 Construct a point set S with n+2 points such that the number of triangulations of S is greater than Catalan number Cn.
Example. See the example in Exercise 3.18 when n gets to 6. □
Exercise 3.17 Compare this value (30n, which is the upper bound of number of triangulations of an arbitrary point set) with Catalan number derived in Theorem 1.19.
Analysis. Number of triangulations of convex hull with n vertices is Cn-2, this number is generally smaller and growing (at a rate lower than 4) much slower than 30n. □
Exercise 3.18 Consider the point set S given in Figure 3.5. It is made of two "double chains" of points, where every pair of points from different chains is visible to each other. Show that the edges drawn in the figure appear in every triangulation of S. Moreover, if there are n points in each chain, find the number of triangulations of S.
Proof. If two points are not connected in a triangulation there must be an edge in the triangulation going across the edge that connects the two points. As every pair of points from different chains is visible to each other, it can be proved that there is no such edge for all the edges drawn in the figure.
Solution to the question. If we use T(m,n) to denote the number of triangulations between the chains of a point set which takes m points from the upper chain and n from the lower chain (it can be proved that this measurement is always applicable to this point set and any of its subsets). It is easy to see the following relationships
T(m,n) = T(n,m)
T(m,n) = T(m-1,n) + T(m,n-1)
T(m,1) = 1
The above relationships lead to T(m,n) = C(m+n-2, m-1) and T(n,n) = C(2n-2, n-1) where C is the combination function.
The polygon enclosed by either of the chain and the horizontal line attached to the chain is a convex polygon so it independently has Catalan(n-2) triangulations, therefore the total number of triangulations is Catalan(n-2)2 C(2n-2,n-1). □
Thursday, May 17, 2012
Exercises of Chapter 2 (Part 4/7), Computational Geometry
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. □
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. □
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.
Monday, April 30, 2012
Exercises of Chapter 1 (Part 4/6), Computational Geometry
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).
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).
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.□
Subscribe to:
Comments (Atom)