Shape Verification
A Simple Algorithm
The previous section showed how to verify a shape. In this section we will discuss a much more interesting problem: shape discovery. Imagine that we are given an unknown convex polygon and that we have to discover its exact shape by probing. The number of vertices is unknown. How many probes are necessary and sufficient to determine the shape of the polygon?
The shape verification solution offers us a partial answer. If the verification of a shape requires exactly 2n probes, a shape cannot be discovered with less than 2n probes. In this section we will show two shape discovery algorithms. The first one requires at most 3n+1 probes to determine the shape of a n-gon. The second algorithm lowers the number of probes to 3n at the cost of added complexity.
|
|
Shape Verification |
A Simple Algorithm |
|