Shape Discovery :: An Improved Algorithm :: 
In this second phase the set of verified edge vertices V is reintroduced. The set V = (p_{0},p_{1},...,p_{m}) contains a sequence of vertices such that each pair of consecutive points in the set are such that the edge between them is verified. At first the input to this phase is the result of the first phase thus V contains either two or three points. This verification phase will also be reused as part of the third phase.
The goal of this phase is to verify the end points of the set V, namely p_{0} and p_{m}. Here the definition of verified vertex is slightly more general than that used previously. A verified vertex is a vertex that is known to be a vertex of the shape S. Verifying a vertex of a semiverified edge of H is simple. Consider the verification of the vertex p_{m}. The edge [p_{m1},p_{m}] is verified which means that it is part of a true edge of the shape S but that the edge of S may be longer. In this phase we send a probe towards p_{m} in the direction of the edge [p_{m1}, p_{m}]. The point at which the probe makes contact gives the extent of the edge in S and thus a vertex of S. This new vertex is by consequence a verified vertex. This phase is illustrated in the following diagrams. Notice that the new verified vertex u replaces p_{m} in V.
There are two additional special cases. The first one is when p_{m}=u, in other words when p_{m} is a true vertex of the shape S. This situation is highly unlikely so Cole and Yap assume that p_{m} is 'infinitesimally displaced' so that p_{m} is never equal to u. The other special case is when u is colinear with an unverified edge of the current hull H. When this happens, a new semiverified edge is added. The second phase must be repeated for the new unverified phase. Consider following example.
This verification process is executed for both end points in the set V, namely p_{0} and p_{m}. The process is repeated until the verification doesn't generate new semiverified edges. It is interesting to note that if the contact point u is above the xaxis then there can be no colinear unverified edges. Thus this process must halt before verifying the entire shape S. Note also that once this process is finished all the points contained in V are verified vertices.

Phase 1: Initialization 
Phase 3: Extension 
