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. □
Subscribe to:
Comments (Atom)