Adversary Algorithm

The algorithm starts by choosing 4 points such that the 3 properties E0, E1 and E2 hold. This essentially means that the convex hull H of the 4 points contains the origin. These four points form the initial set Q. Thus at least 4 points of Q are not contact points resulting from probing. Consequently, at any point in the algorithm the number of  probes is at most k-3 where k+1 is the number of points in Q. This fact will play a crucial role in the proof of our lower bound.

The algorithm then repeatedly determines the appropriate probe outcome such that the three properties hold. Let's consider all possible situations.

Situation 1: The probe L misses R.

Nothing changes. The three hypothesis still hold.

Situation 2: The probe L goes through R but not through H.

The probe L hits one of more W regions of the region R but doesn't hit the current hull H. Notice that it is impossible to draw a line between points in two regions W without going through H unless the two regions are adjacent. Thus probe L can go through at most two neighboring regions W. We will assume that it goes through two regions W and consider the single hit as a special case.

The following figure illustrates this case. The probe hits the region W[p_i, p_i+1] at points r and q. It then hits the region W[p_i-1, p_i]. We first draw lines between p_i and q, and between p_i+1 and r as shown in the following figure. The two lines intersect at a point p'. We then draw a line parallel to the probe that goes through the point p_i. That line intersects one of the diagonals at the point p''.

The adversary chooses a point of contact at infinity. In other words, the probe misses the shape. The set Q is updated by adding a point p chosen randomly in the triangle p_ip'p'' shown in red in the following figure. This choice insures that the three properties are satisfied. E0 is satisfied if we assume that the size of Q hasn't reached 2n yet. Our selection of p guarantees that the new regions W do not intersect with the last probe and thus that E1 is satisfied. Finally E2 is satisfied since no contact points where added.

Why do we have to choose the point p inside the red region? Consider the following example. Let's say that we choose a point p above the diagonal [p_i,q] as shown below. Notice that the resulting region W is inconsistent with the probe outcome and thus breaks property E1. The same thing happens if p is chosen above the other diagonal.

Now consider choosing a point p below the parallel line. Notice that the resulting region W on the left is inconsistent with the probe outcome. 

Thus choosing a point inside the red region guarantees that the three properties hold and gives very little information about the shape to the probing algorithm.

Situation 3: The probe L hits H.

Let's start with the simplest case. The probe goes through a single region W and hits an edge of H. The probe intersect the region W at point q and the edge of H at point r. A point p is chosen on the line joining r to q. This point p is given as a contact point between the probe and the shape. It is added to the set Q so that property E2 holds. Property E1 also holds since the new region R is conform to the new probe outcome. Again property E0 still holds if we assume that the size of Q hasn't reached 2n yet.

Let's now consider the degenerate case in which the intersection between the edge and the probe occurs at one of the bounding vertices. Let's consider first the case in which the probe hits the vertex of H directly without going through a region W, as shown in the following figure. Obviously the probe has no impact on Q and all three properties are maintained.  The point p is given as a contact points by the adversary.

Let's now assume that the probe goes through two regions W as well as a vertex. Again the vertex is given as a contact point. We will still choose another point p that will be added to Q. Consider the following figure. The probe path splits the regions W into four parts. The point p is chosen from within the external part of the region W on the opposite side of the contact vertex with respect to the probe. This insures that the region W on the right clears a path for the probe and thus that property E1 is respected. Properties E0 and E2 are also respected. 

Properties

Proof