Complexity of Probing :: Lower Bound of 3n3 :: 
This proof requires the definition of a few data structures.
P 
The set P is the set of the current probe outcomes. 
Q = (p_{0}, ..., p_{k})  Q is a sequence of k+1 points that represent the vertices (in clockwise order) of a closed convex region H containing the origin. This set is very similar to the 'inside' region defined previously for our shape from probing algorithms. As we will soon see, the vertices in Q may or may not be contact points resulting from probing. 
W[p_{i},p_{i+1}]  The region W[p_{i},p_{i+1}] is formed by extending the edges [p_{i1},p_{i}] and [p_{i+1}, p_{i+2}] in the direction of the edge [p_{i}, p_{i+1}]. The region is either a finite triangle or an infinite trapeze. These two possibilities are shown in the following figure. Note that this region W was used extensively in the previous algorithms to select the best probe (see here). 
R 
The region R is the union of the region H (the convex hull of the points in Q) and the regions W[p_{i}, p_{i+1}] of each pair of points in Q. The regions W tend to be finite as the number of points in Q increases so a typical region R has the following shape:


Lower Bound of 3n3 
Properties 
