Question

what assumption contributes to the linear average - case efficiency of quickhull?
select one
a. points are distributed uniformly over a convex region.
b. points are randomly sorted in increasing x coordinates.
c. points are sorted in decreasing order of y coordinates.
d. points are distributed in a circle.

Explanation:

Quickhull algorithm's average - case efficiency is affected by the distribution of points. When points are randomly sorted in increasing \(x\) coordinates, it helps in the divide - and - conquer approach of Quickhull. Uniform distribution over a convex region (Option A) is more related to the worst - case scenario. Sorting by \(y\) coordinates (Option C) or circular distribution (Option D) does not contribute to the average - case efficiency in the way random sorting in \(x\) coordinates (Option B) does.

Answer:

B. Points are randomly sorted in increasing \(x\) coordinates.