Conclusion
Lower Bound of 3n-3
The previous section described an algorithm capable of determining the shape of a convex n-gon using at most 3n probes. In this section we will study the shape from probing problem to determine lower bounds on the performance of any shape from probing algorithm. More precisely, we will first prove that any shape from probing algorithm can be made to require 3n-3 probes to discover a shape. We will then show that this lower bound can be improved to 3n-1.
The proofs are based on the use of an appropriate adversary that forces the algorithm to make a maximum number of probes. Think of the adversary as a shape that can change its boundary to adapt itself to probes without ever contradicting previous probe outcomes. Whenever the algorithm sends a probe, the adversary chooses a contact point that maximizes the number of remaining probes. The choice of contact points is restricted by the previous probe outcomes since the adversary is not allowed to 'cheat'.
|
|
Conclusion |
Lower Bound of 3n-3 |
|