Shape Discovery :: 

An Improved Algorithm

The previous section described a simple algorithm that discovers the shape of an n-gon using a maximum of 3n+1 probes. In this section, we will described a modified version of this algorithm that reduces the number of probes to 3n. The algorithm is divided in three phases that we will describe shortly. 


Phase 1: Initialization