Say I want to compute a covnex hull of given points on the plane. I would like t

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 ?(nlogn) 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?

Explanation / Answer

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.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.