Introduction

Humans use their five senses to discover the world that surrounds them. Our senses never give us enough information to know the exact nature of that world with certainty. Our vision, for example, doesn't allow us to see the back of objects that we are facing. Nevertheless, our vision of the front of an object is often sufficient to guess what its back looks like. If it looks like a sphere, it probably is a sphere. If we wish to verify our prediction, we simply have to move with respect to the object so that we can see its back.

The sense of touch is similar. Remember the guessing games you played when you were a kid. You're blindfolded and someone hands you an unknown object. Your fingers grasp the object, making contact at only a few points. You move your fingers along the object, making hypothesis about its shape and verifying them with your next gesture. At no point is your body in contact with the entire surface of the object. Yet you are able, with just a few manipulations, to get a mental image of the object.

The same problem presents itself in the world of robotics. Imagine, for example, a robot equipped with a camera and a mechanical probe. It may see an object but be incapable of seeing what's behind it. It may then use it's mechanical probe to poke behind the object and thus discover what it is hiding from the camera. This situation is analogous to our fumbling behind the back of a computer or sound system to find a cable or a switch.

In this tutorial we will study a similar problem in a more theoretical manner. This general class of problems is categorized as the 'shape from probing' problem. Many different assumptions are made about the nature of the shape, the type of probe and the space in which the probing occurs. We limit our study to a narrow class of 'shape from probing' problems. Imagine that we are trying to determine the exact shape of a convex polygon in two-dimensional space. We probe the polygon using directed straight lines similar to fingers in our human analogy. The contact points between the lines and the polygon allow us to discover the shape of the polygon.

This tutorial follows closely a paper titled "Shape from Probing" published in 1987 by Richard Cole and Chee K. Yap [1]. All the results presented herein are due to the work of these researchers and should not be attributed to the humble author of this tutorial. This tutorial simply attempts to present the content of the paper in a more accessible form.

This tutorial begins with a formal definition of the 'shape from probing' problem under consideration. The following section discusses the knowledge gained from the outcome of probes. This is followed by a discussion of the 'shape verification' problem. The next section covers the more interesting problem of 'shape discovery' and describes two algorithms capable of determining the shape of a convex n-gon with 3n+1 and 3n probes respectively. The last section discusses the lower bound on the required number of probes of any 'shape discovery by probing' algorithm. It will be shown that such an algorithm can do no better than requiring a maximum of 

3n-3 probes and we will briefly discuss an improved bound of 3n-1 presented by Cole and Yap.

.

Problem Definition