Convex Hull in no particular order

Question

The proof for the $\Omega(n\log n)$ lower bound for calculating the convex hull by using order-type predicates that I have come across uses the fact that if there was possible to calculate the convex hull in time better than this, then we could do sorting using the same technique, but as it is known that sorting has an lower bound of $\Omega(n \log n)$, hence the lower bound for calculating the convex hull is also the same.

My question is, what if we don't want the convex hull in a cyclic order (clockwise or anticlockwise)? What if we just want the points lying on the convex hull. Surely, in such a case, we can't reduce sorting to this problem and hence the logic for lower bound does not hold. Do there exist any such algorithms? Or some alternative proof that still makes the previous lower bound hold true for this problem?

Answer 1

The generalization of comparison sorting you're looking for is algebraic decision trees. In this model, element distinctness is the standard problem with an $\Omega(n\log n)$ lower bound. The reduction to convex hull is straightforward: $n$ input numbers $x_1,\ldots, x_n$ are distinct if and only if the convex hull of $(x_1,x^2_1), \ldots, (x_n,x^2_n)$.

These lower bounds depend crucially on the decision tree model. For the word RAM, it is a famous result of Chan and Pătraşcu that $o(n\log n)$ is possible.