Question

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

This question was addressed to me during an interview for a job.

My doubt is from Computational Geometry topic in chapter Computational Geometry of Data Structures & Algorithms II

Answer 1

The correct answer is (c) computing convex hull in groups

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