Let's consider the following problem. An hypothesized polygon with n vertices is given. Probing must be used to confirm the hypothesis and thus verify the shape. How many probes are necessary?
The verification of a shape is trivial and consists of two steps.
step 1
Verify the position of the n vertices by sending a single probe towards each of them, carefully avoiding collision with other parts of the polygon. The verification fails if there is an unexpected collision or if the expected collision is missing. Otherwise the vertices are confirmed by contact.
step 2
Verify the n edges of the polygon by sending a single probe towards each of them, avoiding collisions with other parts of the polygon. As explained here, three colinear contact points are sufficient to establish an edge or edge segment of the outer polygon. If the contact points of the probes are colinear with the confirmed vertices then the corresponding edge of the polygon is also confirmed. Otherwise the hypothesis is infirmed and the verification fails.
This simple algorithm requires 2n probes to verify the shape of a n-vertex polygon. Note that 2n probes are both necessary and sufficient to verify the shape. Sufficiency derives from the fact that the above algorithm succeeds for all polygons. Necessity results from the fact that the algorithm is minimal. It's impossible to verify an edge with less than three probes which is precisely the number of probes used per edge.
The following diagram illustrates the verification of a pentahedron. The number of vertices is n=5 which implies that 2n=10 probes are necessary and sufficient to verify the shape.
Although this problem is not very interesting theoretically, it has many applications. A robot, for example, could hypothesize that an object it is facing is a cube using other sensors such as a camera. It could then use a mechanical probe to verify its hypothesis. It's also interesting to consider this problem as a sub-problem of the more challenging shape discovery problem. Indeed the shape discovery problem can be solved by repeatedly making hypothesis about the shape under investigation and proving or disproving them using a verification method, each time learning more information about the shape.
Notice also that the complexity of the shape verification problem implies that an unknown shape cannot be discovered with less than 2n probes.
 |
Summary |
Shape Discovery |
 |