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

Question

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?

Answer 1

Consider the set of points $(0,0),(1,1.2),(0,2),(0.5,0.65)$ versus the set of points $(0,0),(1,1.2),(0,2),(0.5,0.55)$. The last point belongs to the convex hull only in the second set. However, if you compare any two ordinates in the two situations, you will get the same answer.

Answer 2

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.