Question

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

I got this question in an online interview.

I'm obligated to ask this question of Computational Geometry topic in chapter Computational Geometry of Data Structures & Algorithms II

Answer 1

The correct choice is (b) recompute convex hull from scratch

The best I can explain: 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.