[Solved]: Convex Hull algorithm - why it can't be computed using only comparisons

Problem Detail: 

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?

Asked By : Arek Krawczyk

Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/23910