Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question

2 Answers 2

up vote 5 down vote accepted

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.