Cole and Yap [1] include another interesting proof in their paper. They use a method similar to that shown in the previous section to prove that the lower bound on the complexity of any shape discovery algorithm can be raised to 3n-1 probes. The proof for this last results takes 7 pages out of the 19 pages of this paper. It will not be covered in this tutorial.
|
Proof |
Applet |
|