| Complexity of Probing :: Lower Bound of 3n-3 :: |
In order to prove the lower bound on the required number of probes, we will first state 3 properties of the data structures defined in the previous section.
| E0: | The set Q = (p0, ..., pk) contains at most 2n vertices and at least 4. Equivalently, 3 <= k < 2n. |
| E1: | Remember that the outside region has the set of points that can be proven to be outside the shape using the current set of probe outcomes. The intersection between the region R and the outside region is empty. In other words, none of the points inside the region R can be proven to be outside the shape under investigation using the probe outcomes accumulated so far. |
| E2: | All the contact points between probes and the shape are contained in the set Q. |
In the next section we will define an 'adversary' algorithm that insures that these three properties hold for as long as possible. We will then use these results to prove the lower bound of 3n-3 probes.
We will also make an assumption that will allow us to simplify some of our results. Imagine that a probe hits a vertex of the polygon from the side. In other words, imagine that the path of the path overlaps the shape only at a single vertex of the shape. We will assume that such a probe doesn't hit the shape and has a contact point at infinity.
 |
Data Structures |
Adversary Algorithm |
 |