Question

Which of the following algorithms is the simplest?

(a) Chan’s algorithm

(b) Kirkpatrick-Seidel algorithm

(c) Gift wrapping algorithm

(d) Jarvis algorithm

I have been asked this question during an internship interview.

The origin of the question is Computational Geometry topic in chapter Computational Geometry of Data Structures & Algorithms II

Answer 1

Correct choice is (a) Chan’s algorithm

Easiest 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.