Chan's Algorithm Multiple choice Questions and Answers (MCQs)
Chan's algorithm is used for computing .....
Closest distance between two points
Area of a polygon
Shortest path between two points
Question 1 Explanation:
Chan's algorithm is an output-sensitive algorithm used to compute the convex hull set of n points in a 2D or 3D space. Closest pair algorithm is used to compute the closest distance between two points.
What is the running time of Chan's algorithm?
O(n log n)
O(n log h)
Question 2 Explanation:
The running time of Chan's algorithm is calculated to be O(n log h) where h is the number of vertices of the convex hull.
Who formulated Chan's algorithm?
Question 3 Explanation:
Chan's algorithm was formulated by Timothy Chan. Kirkpatrick and Seidel formulated the Kirkpatrick-Seidel algorithm. Frank Nielsen developed a paradigm relating to Chan's algorithm.
The running time of Chan's algorithm is obtained from combining two algorithms.
Question 4 Explanation:
The O(n log h) running time of Chan's algorithm is obtained by combining the running time of Graham's scan [O(n log n)] and Jarvis match [O(nh)].
Which of the following is called the "ultimate planar convex hull algorithm"?
Gift wrapping algorithm
Question 5 Explanation:
Kirkpatrick-Seidel algorithm is called as the ultimate planar convex hull algorithm. Its running time is the same as that of Chan's algorithm (i.e.) O(n log h).
There are 5 questions to complete.