Proof

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 3n-3 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=2n-1. 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 k-3 = 2n-4 probes have been made so far.

At this point we have 2n non-colinear points in Q. The region R has the shape of a star. In order to result in a n-gon, 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 n-gons: 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 n-gons. 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 2n-4 (initial) + 1 (last probe) + n (vertices) = 3n-3 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 3n-3.

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 3n-3 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 3n-4. 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 3n-3 is obtained again.

In all three situations the lower bound is 3n-3.

Adversary Algorithm

Lower Bound of 3n-1