Complexity of Probing :: Lower Bound of 3n3 :: 
In the previous sections we have introduced a set of 3 properties on different data structures and an algorithm that responds to probes in such a way that the three properties are maintained. We will now show that this adversary algorithm can force any algorithm to make at least 3n3 probes.
The adversary algorithm eventually reaches a point at which Q contains 2n points. The next probe's contact point has to be colinear with two other points in the set Q and thus break the second property. Moreover the first property states that the number of points in Q cannot reach 2n+1. At that point, k+1=2n thus k=2n1. We know that at least four of the 2n points in Q are the initial points and thus not contact points, As a result we know that at least k3 = 2n4 probes have been made so far.
At this point we have 2n noncolinear points in Q. The region R has the shape of a star. In order to result in a ngon, exactly half of the edges in H are part of the true edges in the shape S. Moreover, the symmetry in the polygon H implies that these true edges must alternate. Thus there are only two possibly ngons: P1 and P2. Consider the following example. The figure on the left shows the region R with the regions W in gray. The two figures on the right show the only two possible ngons. Thus the adversary still has to choose one of the two options, after which its shape is completely defined.
Let's consider the next probe. Three situations are possible:
Situation 1: Probe intersects the interior of R.
The adversary chooses P0 or P1 so that the probe doesn't hit a corner of the shape. As a result, the shape from probing algorithm still has to verify the n vertices of the polygon. This results in a minimum number of probe of 2n4 (initial) + 1 (last probe) + n (vertices) = 3n3 probes.
Situation 2: Probe misses R entirely.
The adversary chooses between P0 and P1 at random. The algorithm still has to verify the n vertices resulting in the same lower bound of 3n3.
Situation 3: Probe intersects the boundary of R
This situation occurs if the probe path goes through the apex of one or two of the regions W. If a single apex is hit, the adversary picks P0 or P1 so that the probe misses the shape. This results in a lower bound of 3n3 again.
Now consider the second case in which the probe passes through two apex. One of the two has to be a vertex of the shape S. This would eliminate the need to verify one of the vertices and thus cause the lower bound to decrease at 3n4. Remember however our assumption about lateral probes. We are assuming that a probe whose path intersect only a single vertex misses the shape. Thus the probe misses the shape in this situation and a lower bound of 3n3 is obtained again.
In all three situations the lower bound is 3n3.

Adversary Algorithm 
Lower Bound of 3n1 
