Conclusion

The complexity of the algorithm can be analyzed through the properties holding in the third phase. The second property implies that each of the m verified edges of the set V have 2 internal contact points except one which might have three. The total thus comes to 2m+1 internal contact points. Note however that the algorithm halts by finding a single contact point between two vertices. Thus one of the edges can be proven to have a single internal contact point instead of the maximum of 2. This edge creates an equilibrium with the exceptional edge having a maximum of 3 internal contact points. Thus the maximum number of internal contact points is only 2n. Adding the n vertices we get a total of 3n probes.

The modified algorithm requires a maximum of 3n probes instead of the 3n+1 probes required by the original algorithm.

This modified algorithm saves a single probe. Cole and Yap mention that this saving is obtained at a significant cost. Obviously this algorithm is much more complicated. Moreover the probing method used in the second phase is known to be unstable. Indeed one can easily imagine missing the vertex of the shape and probing to infinity when some noise is present.

Phase 3: Extension

Complexity of Probing