Phase 1: Initialization

The algorithm begins by sending three probes towards the origin from below the x-axis. Our assumption about the shape S implies that all three initial contact points are also below the x-axis. The initial current hull H is thus (p₀,p₁,p₂). The first phase halts as soon as the current hull H contains a verified edge. This implies that the algorithm proceeds to the next phase right away if the three initial points are colinear, thus defining a verified edge.

The first phase keeps probing the shape S until a verified edge is found. The probe selection is identical to that of the original algorithm. More precisely, an attempt is made to verify an edge of the current hull H by sending a probe towards both the edge under consideration and the vertex of a triangle formed by the two unverified edges surrounding it. The algorithm tries to verify edges under the x-axis. It is thus guaranteed to hit the shape S only below the x-axis. Each probe can result in three outcomes as explained at length in previous sections:

1. The probe hits the apex of the triangle. Two edges are verified and the algorithm proceeds to the next step.

2. The probe hits the edge. The edge is verified and the algorithm proceeds to the next step.

3. The probed hits a point inside the triangle. A new unverified edge is added. This phase continues and another probe is made.

Note that this step is guaranteed to succeed with at most 2n+1 probes. Indeed the polygon has n faces so 2n+1 probes are guaranteed to hit at least a single edge more than twice, resulting in a verified edge.

An Improved Algorithm

Phase 2: Verification