I have heard that the quickhull algorithm can be modified if the size of the convex hull (the number of points it consists of) is known beforehand, in which case it will run in linear time. What modifications are required in order to decrease the time complexity of the convex hull algorithm?
1 Answer
$\begingroup$
$\endgroup$
It is not true. As you know, we can reduce sorting numbers to finding convex hull (see here). So, we know that size of the convex hull, in this case, is $N$. However, we can't compute convex hull in nearly linear time! as lower bound for sorting numbers in general case is $\Omega(n\log n)$.
Anyhow, we have an algorithm to finding convex hull which is output-sensitive and can be run in $O(n\log h)$, which $h$ is the size of convex hull (see here). Hence, if you know the size of the convex hull such that its size is constant, you can compute convex hull in linear time.
