|Shape Discovery :: A Simple Algorithm ::|
In this section we analyze the algorithm to prove both its correctness and an upper bound on the number of probes. Two observations are made about the data structures. It is shown that these two observations or inductive hypothesis hold all through the execution of the algorithm. These observations are then used to prove the correctness and complexity of the algorithm.
The set of verified edges of H forms a contiguous sequence. 
This fact follows from our definition of the algorithm.
Initially none of the edges are verified. The algorithm picks a starting
point and tries to verify the first edge. It then keeps trying to verify
the next unverified edge. Whenever the algorithm attempts to verify an edge,
we are guaranteed that the edge that immediately precedes it has already
been verified. Thus the verified edges of H form a contiguous sequence. The
following diagram shows an example of a sequence of verified edges. See
the vocabulary section
for the appropriate legend. (dotted lines: unverified; thin line: semi-verified;
thick line: fully-verified)
At most one edge in H doesn't have these properties:
The exceptional edge, if there is one, has 3 internal contact points if fully-verified and 2 internal contact points otherwise. The exceptional edge is the first edge in V and the last one to be fully-verified.
1. Semi-verified edges have exactly one contact point in their interior.
2. Fully-verified edges have either 1 or 2 contact points in their interior.
These three cases represent all possible probe outcomes. As a result
semi-verified edges have a single internal contact point and fully-verified
edges have either one or two internal contact points. The only exception is due to the final edge that gets fully
verified. Under some special circumstances, the first edge of the sequence will
have two internal contact points while semi-verified and three contact points
when fully-verified. This situation occurs when the first two contact points in
the initial sequence of four fall on an edge of the polygon but not on the
vertices. This is illustrated in the following animation.
These observations allow us to reach some conclusions about the correctness and complexity of this algorithm. First notice that there can be no more than n verified edges since there are n edges in the polygon. In the end we thus have a total of n fully-verified edges corresponding to the true edges of the polygon. Observation 2 tells us that each fully-verified edge has a maximum number of two internal contact points, except one edge which might have three internal contact points. The maximal number of probes is thus 3n+1 (2n+1 internal contact points plus n vertices).
The simple algorithm requires at most 3n+1 probes to discover the shape of an n-vertex polygon.
The algorithm keeps verifying unverified edges in sequence, always verifying the edge following the last verified edge. At each step, either the number of verified edges is increased or the number of unverified edges increases. The algorithm stops only when all edges are verified, which implies that the correct polygon is found. Moreover we have already seen that the number of probes is bounded so the algorithm will stop. The algorithm is thus correct.
An Improved Algorithm