Convex Quadrilateral 2 (loud)
- Author:
- Ryan Hirst
In Cormen's Algorithms, the convex hull methods only give a hull on the very last step.
Slumberland thinks that a somewhat klunkier method per-step, but which gives a bounding hull at every step, is much more promising. The convex hull is a limit position: the smallest convex polygon which contains the given points. So a good solution will observe the definition of the problem. A limit position can be refined from an estimate. In the present case, any bounding estimate can be refined in a number of ways.
He also thinks that, for the same reasons, running time is measured badly. For suppose we argue this way:
The time it takes for Cormen's algorithm to give a hull increases without bound as a function of the input size. The order of the leading term is not 1. That is, as n increases, linear time is dwarfed by the leading term. But the running time for Slumberland to give a hull is ignored by Cormen altogether: the time to presort the data. Say, find the greatest and least x,y,.... values from the list, and draw a box/cube....
That is, Slumberland and Cormen are in perfect agreement: for arbitrary input size and worst-case analysis, the time it takes for Cormen to have a polygonal hull is so much greater than Slumberland, that there is no point whatever in comparing the two.
In fact, Cormen will go further; he will discard the lower-order term altogether argue that, by relative comparison, Slumberland has a hull instantaneously. Slumberland thinks this is a ridiculous way to measure, for the relative comparison does not obtain as promised, as just illustrated. The trick of measuring is to measure, not tell valid stories starring logic.
Lastly, he thinks that a scheme which can allow the point set to be partitioned and managed in parallel will be superior.
Now. Slumberland is convinced that the method he outlined in this worksheet is inefficient, and poorly defined for parallel implementation. Slumberland has only a slow step 1. Cormen has a working solution to the general problem.
How might Mr. the Land improve his method? What are the terms of the problem? Can he make good on his thinking?
(Hint: we are free to partition space however we wish.)