Convex Hull algorithm - why it can't be computed using only comparisons

Say I want to compute a covnex hull of given points on the plane. I would like to write an algorithm, that only compares the points and doesn't do any arithmetic operations. Wikipedia states, that:


The standard $\Omega(n \log n)$ lower bound for sorting is proven in the decision tree model of computing, in which only numerical comparisons but not arithmetic operations can be performed; however, in this model, convex hulls cannot be computed at all.

Why is it so? I can't find any justification for it anywhere, I know it to be intuitively true, but how come it's a necessity?

For a slightly more general way of looking at this, what you want to do is equivalent to saying you can reconstruct the convex hull from the orderings induced by projections onto the coordinate axes.

To see you can't do this, just observe that for three points $a$, $b$, and $c$, knowing that $a < c < b$ in both projections doesn't let you figure out whether $c$ is above, below, or on the segment $ab$. (Start with $c$ on the segment and then perturb it up or down by a small amount.)

This indicates that you'll need the "left turn" and "right turn" predicates.

StackExchange Computer Science Q#23910, answer score: 6