Tham khảo tài liệu 'thuật toán algorithms (phần 35)', khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | FINDING THE CONVEX HULL 333 Exercises 1. Suppose it is known in advance that the convex hull of a set of points is a triangle. Give an easy algorithm for finding the triangle. Answer the same question for a quadrilateral. 2. Give an efficient method for determining whether a point falls within a given convex polygon. 3. Implement a convex hull algorithm like insertion sort using your method from the previous exercise. 4. Is it strictly necessary for the Graham scan to start with a point guaranteed to be on the hull Explain why or why not. 5. Is it strictly necessary for the package-wrapping method to start with a point guaranteed to be on the hull Explain why or why not. 6. Draw a set of points that makes the Graham scan for finding the convex hull particularly inefficient. 7. Does the Graham scan work for finding the convex hull of the points which make up the vertices of any simple polygon Explain why or give a counterexample showing why not. 8. What four points should be used for the Floyd-Eddy method if the input is assumed to be randomly distributed within a circle using random polar coordinates 9. Run the package-wrapping method for large points sets with both X and y equally likely to be between 0 and 1000. Use your curve fitting routine to find an approximate formula for the running time of your program for a point set of size N. Use your curve-fitting routine to find an approximate formula for the number of points left after the Floyd-Eddy method is used on point sets with x and y equally likely to be between 0 and 1000. 26. Range Searching Given a set of points in the plane it is natural to ask which of those points fall within some specified area. List all cities within 50 miles of Providence is a question of this type which could reasonably be asked if a set of points corresponding to the cities of the . were available. When the geometric shape is restricted to be a rectangle the issue readily extends to non-geometric problems. For example list all .
