Chan’s Algorithm Multiple Choice Questions and Answers (MCQs)

«
»

This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Chan’s Algorithm”.

1. Chan’s algorithm is used for computing _________
a) Closest distance between two points
b) Convex hull
c) Area of a polygon
d) Shortest path between two points
View Answer

Answer: b
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.
advertisement

2. What is the running time of Chan’s algorithm?
a) O(log n)
b) O(n log n)
c) O(n log h)
d) O(log h)
View Answer

Answer: c
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.

3. Who formulated Chan’s algorithm?
a) Timothy
b) Kirkpatrick
c) Frank Nielsen
d) Seidel
View Answer

Answer: a
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.

4. The running time of Chan’s algorithm is obtained from combining two algorithms.
a) True
b) False
View Answer

Answer: a
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)].

5. Which of the following is called the “ultimate planar convex hull algorithm”?
a) Chan’s algorithm
b) Kirkpatrick-Seidel algorithm
c) Gift wrapping algorithm
d) Jarvis algorithm
View Answer

Answer: b
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).
advertisement

6. Which of the following algorithms is the simplest?
a) Chan’s algorithm
b) Kirkpatrick-Seidel algorithm
c) Gift wrapping algorithm
d) Jarvis algorithm
View Answer

Answer: a
Explanation: Chan’s algorithm is very practical for moderate sized problems whereas Kirkpatrick-Seidel algorithm is not. Although, they both have the same running time. Gift wrapping algorithm is a non-output sensitive algorithm and has a longer running time.

7. What is the running time of Hershberger algorithm?
a) O(log n)
b) O(n log n)
c) O(n log h)
d) O(log h)
View Answer

Answer: b
Explanation: Hershberger’s algorithm is an output sensitive algorithm whose running time was originally O(n log n). He used Chan’s algorithm to speed up to O(n log h) where h is the number of edges.

8. Which of the following statements is not a part of Chan’s algorithm?
a) eliminate points not in the hull
b) recompute convex hull from scratch
c) merge previously calculated convex hull
d) reuse convex hull from the previous iteration
View Answer

Answer: b
Explanation: Chan’s algorithm implies that the convex hulls of larger points can be arrived at by merging previously calculated convex hulls. It makes the algorithm simpler instead of recomputing every time from scratch.

9. Which of the following factors account more to the cost of Chan’s algorithm?
a) computing a single convex hull
b) locating points that constitute a hull
c) computing convex hull in groups
d) merging convex hulls
View Answer

Answer: c
Explanation: The majority of the cost of the algorithm lies in the pre-processing (i.e.) computing convex hull in groups. To reduce cost, we reuse convex hulls from previous iterations.
advertisement

10. Chan’s algorithm can be used to compute the lower envelope of a trapezoid.
a) true
b) false
View Answer

Answer: a
Explanation: An extension of Chan’s algorithm can be used for proving solutions to complex problems like computing the lower envelope L(S) where S is a set of ‘n’ line segments in a trapezoid.

Sanfoundry Global Education & Learning Series – Data Structures & Algorithms.

To practice all areas of Data Structures & Algorithms, here is complete set of 1000+ Multiple Choice Questions and Answers.

Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

advertisement
advertisement
advertisement
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn