Conclusion

This tutorial has explained in details most of the results contained in "Shape from Probing" by Cole and Yap [1]. We first defined the shape from probing problem. We then showed a trivial solution to the shape verification problem. 

The next section showed two versions of a shape discovery algorithm. The first one requires 3n+1 probes for an n-gon but is relatively simple to understand and implement. The second algorithm reduces the number of probes to 3n. It is, however, fairly difficult to understand and implement. Whether or not a gain of a single probe justifies the added complexity is questionable. 

The next section first proved that no shape discovery can do better than an upper bound of 3n-3 probes. A tighter bound of 3n-1 was then reported based on the Cole and Yap paper [1] without being proved. It is interesting to note that the modified shape discovery algorithm is one probe away from the theoretical optimal algorithm, if such an algorithm exists.

This tutorial was limited to a very small subset of the possible shape from probing problems. Consider, for example, the added complexity introduced by probing a three-dimensional object or by probing a non-convex shape. For further readings, I suggest Matt Holly's tutorial which describes a similar problems with a different probe definition [3].

Applet

References